题目

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");
    }
}