数组 两数之和

[SummerXinBing]

暴力解决 时间复杂度o(n^2) 空间复杂度o(1)

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

[SummerXinBing]

使用hash

// 本质还是搜索target-x;但是使用数据结构将时间复杂度降到o(n),hash的搜索o(1)
    // map的两个api boolean containKey(Object key) boolean containValue(Object value)
    public static int[] twoSum(int[] nums, int target) {
        int length = nums.length;
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for (int i = 0; i < length; i++) {
            int x = nums[i];
            if (map.containsKey(target - x)) {
                return new int[]{i,map.get(target-x)};
            }
            map.put(x,i);
        }
        return new int[0];
    }