[LeetCode] 1. Two Sum (easy)

Welcome To My Blog

1. Two Sum (esay)

1.1.png

Brute Force

1. 直接通过两个元素满足的等式关系寻找,即 a + b = target,选定一个a,则b = target - a,遍历数组,看看有没有值为b的元素
2. Complexity Analysis
   • Time complexity : O(n^2)
   • Space complexity: O(1)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[]{i, j};
                }
            }
        }
        //没有找到则抛出异常
        throw new IllegalArgumentException("No solution!");
    }
}

使用 Hash Table

1. 使用 Hash Table可以快速判断数组中有没有相应元素,这是一种通过消耗空间从而减少时间的方案
2. Complexity Analysis
   • Time complexity : O(n)
   • Space complexity: O(n)

public int[] twoSum(int[] nums, int target) {
    //1. 先建立元素值与元素位置的映射
    Map<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; i++){
        int b = target - nums[i];
        //2. 要记得排除target - a是自身的情况
        if (map.containsKey(b) && map.get(b) != i) 
            return new int[] {i,map.get(b)};
    }
    //3. 字符串要用双引号
    throw new IllegalArgumentException ("No solution!");
}

3. 上面使用两个循环,其实一个循环就可以了,边插入元素边判断:将要插入map中的元素跟存在于map中的元素去比,complexity analysis跟上面一样

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++){
        int b = target - nums[i];
        //这里不需要 && map.get(b) != i,因为当前元素并没有放到map中
        if(map.containsKey(b)) 
            return new int[] {i,map.get(b)};
        else map.put(nums[i],i);
    }
    throw new IllegalArgumentException("No solution!");
}