Advanture 1 - leetcode 1 - Two Sum

Posted on In Views: Views:

leetcode解题思路总结:

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
链接:

示例:

1
2
3
4
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

对于这样的题目，最容易想到的是brute-force暴力解法, 直接两重循环进行迭代.

1
2
3
4
5
6
7
8
9
10
11
12
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};
            }
        }
        // Returns null if solution not found.
        return null;
    }
}

复杂度分析(Complexity Analysising):

  • 时间复杂度(Time complexity): O(n2)O(n^2)
  • 空间复杂度(Space complexity): O(1)O(1)

暴力解法虽然可行，但是时间复杂度为O(n2)O(n^2), 考虑进行优化，首先想到是可以以空间换时间:

如果能够把给定数组的数，用某种数据结构将每个数的数值以及对应的索引(index)保存起来，则只需要用一次遍历查找
target - nums[i]是否存在于该数据结构中，且非nums[i]即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] twoSum(int[] nums, int target) {
        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 remain = target - map.get(nums[i]);
            if (map.containsKey(remain) && map.get(remain) != i)
                return new int[] {i, map.get(remain)};
        }
        // returns null if solution not found.
        reutrn null;
    }
}

复杂度分析(Complexity Analysising):

  • 时间复杂度(Time complexity): O(n)O(n)
  • 空间复杂度(Space complexity): O(n)O(n)

年轻的我，本以为上面的这种解法已经是最优的了，但是看完讨论区之后，才焕然大悟，它还可以进行优化:
仔细看的话，上面的HashMap算法访问了nums数组两遍，而接下来，从leetcode上学习到的优化方法就是将nums数组的访问从两遍降到一遍.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int remain = target - nums[i];
            if (map.containsKey(remain))
                return new int[] {map.get(remain), i};
            map.put(nums[i], i);
        }
        return null;
    }
}

由于map中保存的肯定是索引i之前的数，因此不需要判断map.get(remain) != i.

复杂度分析(Complexity Analysising):

  • 时间复杂度(Time complexity): O(n)
  • 空间复杂度(Space complexity): O(n)

总结

对于能够快速使用brute-force暴力解法解决的问题，考虑优化时，首先考虑能够减少循环的嵌套，其次是考虑减少数组的访问次数、元素比较次数、元素交换次数等。