1. 两数之和

1. 两数之和

暴力枚举

时间复杂度 O(n^2)，

执行用时：55 ms, 在所有 Java 提交中击败了28.85%的用户 内存消耗：38.4 MB, 在所有 Java 提交中击败了85.38%的用户

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) return new int[] {i, j};
            }
        }
        return null;
    }
}

哈希表

上面方法复杂度高的原因在于查找 nums[i] + nums[j] == target 这步操作的复杂度过高，可以考虑使用哈希表把这步操作优化为 O(1)

执行用时：4 ms, 在所有 Java 提交中击败了52.84%的用户 内存消耗：39.7 MB, 在所有 Java 提交中击败了5.04%的用户

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length - 1; i++) {
            Integer exists = map.get(target - nums[i]);
            if (exists != null && exists != i) {
                return new int[]{i, exists};
            }
        }
        return null;
    }
}