抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

15 | 面试题:两数之和

题目

1. 两数之和

解法一:暴力求解

写嵌套循环,遍历元素,求得 X + Y = 目标值,注意:X、Y不能重复使用,X从0循环到length-1,Y则从X+1循环到最后。

时间复杂度:O(N²)

class Solution {
fun twoSum(nums: IntArray, target: Int): IntArray {
for (i in nums.indices) {
for (j in i + 1 until nums.size) {
if (nums[j] == target - nums[i]) {
return intArrayOf(i, j)
}
}
}
throw IllegalArgumentException("No two sum solution")
}
}

解法二:使用数据结构 SET,特点:X + Y = 9 可以推出 Y = 9 – X

思路:可以写一个 for 循环枚举 X,X 枚举范围从 0 到 length。然后去 SET 中查找9 – X 是否在数组中存在即可。

细节:每一次循环 X 时需要先从SET 中去掉。或者记录哪些元素用过哪些元素没用过。

时间复杂度:O(N)

同时由于需要返回坐标,使用 MAP 替代 SET,最终逻辑:

MAP结构:{值 : 下标},遍历 X,计算 Y 值,检测 map 中是否包含 Y 值,不包含则将 X 放入 map,包含则通过 map返回 Y 值的坐标与 X 的下标。

返回的 y 的下标为什么在前面可能需要解释一下:一开始 map 为空,这时 y 是无法找到的,后面 map 填充后,map 中的元素实际上是前面的元素,所以需要颠倒一下,相当于从后往前找,想不明白的用 debug 调试跟踪一下。

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map= mutableMapOf<Int, Int>()
        for (i in nums.indices) {
            val complement = target - nums[i]  //y 值
            if (map.containsKey(complement)) {
                val y = map[complement]?: throw IllegalArgumentException("No two sum solution") //y 的下标
                return intArrayOf(y, i)
            }
            map[nums[i]] = i
        }
        throw IllegalArgumentException("No two sum solution")
    }
}

Java代码:

class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}

0条评论

发表评论