推荐点击查看原文,体验更佳~
1. 两数之和
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
暴力解、优化
第一时间想到使用双指针,依次遍历相加并判断是否等于 target。
代码如下:
fun twoSum(nums: IntArray, target: Int): IntArray {
if (nums.isEmpty()) {
return IntArray(0)
}
var resultArray = IntArray(2)
var isl = false
var i = 0
var j = 1
while (i < nums.size - 1){
while (j < nums.size){
if (nums[i] + nums[j] == target) {
resultArray[0] = i
resultArray[1] = j
isl = true
break
}
j++
}
if (isl) {
break
}
i++
j = i + 1
}
return resultArray
}
执行结果:
个人简单分析下时间复杂度:
第一次尝试分析,不对之处欢迎指点~
反思了下,可以直接在符合条件下直接 return,修改后代码如下:
fun twoSum(nums: IntArray, target: Int): IntArray {
if (nums.isEmpty()) {
return IntArray(0)
}
var resultArray = IntArray(2)
var i = 0
var j = 1
while (i < nums.size - 1){
while (j < nums.size){
if (nums[i] + nums[j] == target) {
resultArray[0] = i
resultArray[1] = j
return resultArray
}
j++
}
i++
j = i + 1
}
return resultArray
}
执行结果:
再想想,似乎有些变量无需创建,直接 return 多好?
fun twoSum(nums: IntArray, target: Int): IntArray {
if (nums.isEmpty()) {
return intArrayOf(0,0)
}
var i = 0
var j = 1
while (i < nums.size - 1){
while (j < nums.size){
if (nums[i] + nums[j] == target) {
return intArrayOf(i,j)
}
j++
}
i++
j = i + 1
}
return intArrayOf(0,0)
}
执行结果:
学习 LeetCode 执行用时最短事例
fun twoSum(nums: IntArray, target: Int): IntArray {
if (nums.isEmpty()) {
return intArrayOf(0, 0)
}
for (i in nums.indices) {
for (j in 0..i) {
if (i == j) {
continue
}
val a = nums[i];
val b = nums[j];
if (a + b == target) {
return intArrayOf(j, i)
}
}
}
return intArrayOf(0, 0)
}
执行结果:
有点尴尬,尝试了几次,还不如我最终的优化执行结果,不过也是一种方式。
学习 LeetCode 执行消耗内存范例
使用 HashMap 方式确实没有想到,不过思路还是蛮不错的,个人简要分析一波:
有关详情,查阅代码:
fun twoSum(nums: IntArray, target: Int): IntArray {
if (nums.isEmpty()) {
return intArrayOf(0, 0)
}
val map: MutableMap<Int, Int> = HashMap()
for (i in nums.indices) {
val complement = target - nums[i]
if (map.containsKey(complement)) {
return intArrayOf(map[complement]!!, i)
}
map[nums[i]] = i
}
throw Exception()
}
执行结果:
题外话
没明白为啥执行 LeetCode 几次结果不是 100%,不过也没关系,比较学习算法最终目的并不是求最优解,而是通过一次次的分析、优化,让个人思维进行一个提升。个人感觉是这样的。
自己摸索,查看范例。一起努力,加油~
Thanks
LeetCode 历史文章