1. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

思路一：

暴力法：

  • 两遍for循环，从头开始遍历元素与后边元素依次相加和target比较
  • 当和target相等时， 则为最终结果
  • 遍历到尾部都不同时，开始第二轮循环
  • 第二个元素执行上述操作
  • ….
  • 循环到末尾仍然没有元素之和 == target时，return null
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

    // 暴力法 - 两层循环
    public int[] twoSum(int[] nums, int target) {

        for (int i = 0; i < nums.length; i++) {
            int m = nums[i];
            for (int j = i+1; j < nums.length; j++) {
                int n = nums[j];
                if (m + n == target){
                    int [] res = {m,n};
                    return res;
                }
            }
        }
        return null;
    }

复杂度分析:

时间复杂度 : O(N ^ 2)

空间复杂度: O(1)

暴力破解虽然 ac，但是执行用时特别长，

思路二：

HashMap

  • 以空间换时间的思想

  • 用HashMap存储 <差值 : index>

  • 遍历数组， 如果map的key中包含当前元素的值。

    • 说明当前元素的值 + map中取出的下标处指向的值和为 target

  • 如果map的key中不包含当前元素的值

    • 则将 target 与 当前元素的差值 : 当前元素下标 存入字典

  • 遍历完毕，如果没有找到一对元素和为target， 则return null

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// 利用hashmap减少查询时间
/*
* HashMap中保存{差值 ：index}
* 遍历， 如果map的key包含 取到的值。则取出i和 key对应的value
* */
public int[] twoSum1(int[] nums, int target) {

    HashMap<Integer,Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int m = nums[i];
        if (map.containsKey(m)){
            int [] res = {map.get(m),i};
            return res;
        }
        map.put(target - m,i);
    }
    return null;
}

复杂度分析 ：

时间复杂度 : O(N) 遍历一遍数组

空间复杂度 : O(N) 利用了额外的字典存储空间

题目进阶：

167. 两数之和 II - 输入有序数组

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。 示例:

输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

此题目与上边的题目非常类似, 唯一区别之处在于，本题中的数组是有序的

仍然可以用上题中，两种解法解决。

思路一：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 *
 * 暴力法，两层循环
 * 时间复杂度 : O(N ^ 2)
 * 空间复杂度 : O(1)
 *
 * 代码逻辑简单，粗暴
 *
 * */
public int[] twoSum(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        int m = numbers[i];
        for (int j = i+1; j < numbers.length; j++) {
            int n = numbers[j];

            if (m + n == target){
                int [] res = {m + 1,n + 1};
                return res;
            }
        }
    }

    return null;
}

暴力法

思路二：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 *
 * 字典存储遍历过的值
 *
 * 用map 存储 <target - num, num>. 遍历下一个元素时，如果 map的key中包含。说明和为target。
 * 遍历完毕，没找到，则返回空
 *
 * 时间复杂度 : O(N)
 * 空间复杂度 : O(N)
 *
 * */
public int[] twoSum1(int[] numbers, int target) {
    HashMap<Integer,Integer> map = new HashMap<>();
    for (int i = 0; i < numbers.length; i++) {
        int num = numbers[i];
        if (map.containsKey(num)) {
            int[] res = {map.get(num),i};
            return res;
        }
        map.put(target-numbers[i], num);
    }
    return null;
}

哈希表

思路三：

以上两种解法中，我们完全没有用到有序数组这个条件。

那么，如何利用有序这个条件呢？

看到有序，首先想到的是不是可以用二分查找？

用二分查找进行了尝试，发现不太好实现。

  • 因为一个最小的数字和一个最大的数字，和有可能刚好为target
  • 二分方貌似不能缩小范围。

所以，我们利用本题中的双指针法解决问题

  • 首先用两个指针 begian = 1, end = nums.length - 1; 分别指向数组的开头和末尾
  • while循环(循环条件 begain < end)，计算两个指针指向元素的和sum
    • 当sum == target时，begain 和 end 即为最终结果
    • 当sum > target时, begain –
    • 当sum < target时, end ++
  • 循环过程中，一直没有 sum == target 的情况，则返回null
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**
 * 因为我们完全没有用到升序数组这个条件
 * 因为时有序数组，所以想到使用二分的思想解决问题
 *
 * 但是试着写了一会代码，发现二分的思想貌似不能用
 * 因为一个最小的数字 + 一个最大的数字。 有可能和刚好为 target
 * 所以二分没办法缩小查找范围。不能用
 *
 * 所以我们利用，双指针法解决
 * 两个指针分别指向数组的开头begain和结尾end
 * 依次计算两个指针指向元素的和
 *   如果刚好等于 target 则为最终结果
 *   如果 大于 target。 则 end --； 继续循环
 *   如果 小于 target。 则 begain ++； 继续循环
 *   循环条件 begian < end
 */
public int[] twoSum2(int[] numbers, int target) {
    int begain = 0, end = numbers.length - 1;
    while (begain < end){
        int num1 = numbers[begain];
        int num2 = numbers[end];

        if (num1 + num2 == target) {
            int[] res = {begain, end};
            return res;
        }

        if (num1 + num2 > target)
            end --;
        else
            begain ++;
    }

    return null;
}

双指针

复杂度分析 :

时间复杂度 : O(N)

空间复杂度 : O(1)

进阶-三数之和

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/3sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

思路一：暴力法

  • 最容易想到的方法-暴力法
  • 三层循环，找到每一种不同数字可能的组合
  • 当三个数字和为0时，添加到结果数组
  • 时间复杂度 : O(N ^ 3)
  • 空间复杂度 : O(1)

思路二：排序 + 双指针

  • 先排序
  • 排序后，两层循环数组
  • 取到最外层某个数字num
    • 开始计算其后边 n-1个元素的和 为 -num 的组合
    • 因为已排序，所以可以用 头尾双指针法 计算后边 n-1个元素的和
    • 头尾双指针 begain， end
      • 当和 == -num时， 加入结果数组
      • 当和 < -num时， begain++
      • 当和 > -num时， end –

❗️❗️❗️

  • 在确定此题目 排序 + 双指针 的解题思路后
  • 本题难点在于，如何去除重复解
  • 我没写好，copy的评论区的代码😅😅😅
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

 /**
     *
     * 先排序
     * 排序后，数组两层循环
     * 取到最外层某个数num
     *    开始计算其后边 n - 1个元素的和为 -num 的组合
     *    后边的操作 类似 排序版本 的两数之和
     *    头尾双指针begain, end，
     *      当和 == -num时, 加入结果数组
     *      当和 < -num时, begain ++
     *      当和 > -num时, end --
     *
     *
     * */
    public static List<List<Integer>> threeSum(int[] nums) {

        // 先排序
        Arrays.sort(nums);
        List<List<Integer>> ls = new ArrayList<>();

        // 排序以后的操作 跟 排序后的两数之和一样
        for (int i = 0; i < nums.length - 2; i++) {
            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {  // 跳过可能重复的答案

                int l = i + 1, r = nums.length - 1, sum = 0 - nums[i];
                while (l < r) {
                    if (nums[l] + nums[r] == sum) {
                        ls.add(Arrays.asList(nums[i], nums[l], nums[r]));
                        while (l < r && nums[l] == nums[l + 1]) l++;
                        while (l < r && nums[r] == nums[r - 1]) r--;
                        l++;
                        r--;
                    } else if (nums[l] + nums[r] < sum) {
                        while (l < r && nums[l] == nums[l + 1]) l++;   // 跳过重复值
                        l++;
                    } else {
                        while (l < r && nums[r] == nums[r - 1]) r--;
                        r--;
                    }
                }
            }
        }
        return ls;
    }

复杂度分析 :

时间复杂度 : Arrays.sort() 最优的快排，时间复杂度为 O(N * log N) 。 后边的两层循环 : O(N ^ 2)

所以整体时间复杂度 : O(N * logN) + O(N ^ 2) = O(N ^ 2)

空间复杂度 : 除结果数组以外，没有用到额外的存储空间，所以为 O(1)

三数之和再变种：

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

3 <= nums.length <= 10^3 -10^3 <= nums[i] <= 10^3 -10^4 <= target <= 10^4

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/3sum-closest 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

  • 本题目是15题 三数之和 的变种
  • 15题中，我们采用 排序 + 双指针 的解法
  • 本题中，貌似我们依然可以采用这种解法
  • 只不过15题是 在遍历过程中， 将和 == target的数依次加入数组
  • 本题中，只要保存最接近的值即可
  • 这样想，貌似题目还简单了，因为不需要去除麻烦的重复
  1. 依然是排序
  2. 遍历排序后的数组 ，头尾双指针解题方法
  3. 求 三个数的和 和 target差值的绝对值
  4. 当最近求出的 差值的绝对值 < 之前求的结果， 则替换结果。
  5. 遍历过程中
    1. 当 sum == target时，差值0，直接return sum
    2. 当 sum > target时，right–，找是否有更接近的
    3. 当 sum < target时，left++, 找是否有更接近的
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public static int threeSumClosest(int[] nums, int target) {

				// 先排序 时间复杂度 O(N * log N)
        Arrays.sort(nums);

        int res = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int left = i + 1, right = nums.length - 1;
            while (left < right){
                int sum = nums[left] + nums[right] + num;
                // 如果有相等的，直接返回0
                if (sum == target) return sum;
                if (Math.abs(sum - target) < Math.abs(res - target))
                    res = sum;

                if (sum > target){
                    right --;
                }else {
                    left ++;
                }
            }
        }
        return res;
    }

复杂度分析 :

时间复杂度 : O(N ^ 2)

空间复杂度 : O(1)

截屏2020-06-24上午11.12.15

进阶： 四数之和

18. 四数之和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

leetcode 也是挺有意思，两数之和，两数之和I，两数之和II, 三数之和…现在又来一个四数之和

让我想起了 丑数I, 丑数II, 丑数III, 超级丑数

以后会来一个 N数之和 或者 超级N数之和的吧.

  • 其实跟三数之和相比， 也没啥新意
  • 一样的套路，先排序，后循环
  • 无非是内部三层循环，还是两层循环的问题
  • 但是做过三数之和的同学都知道，去重复的恶心…
  • 去重复去的想吐..
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();

        // 先排序
        Arrays.sort(nums);
        List<List<Integer>> ls = new ArrayList<>();

        // 排序以后的操作 跟 排序后的两数之和一样
        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            for (int j = i + 1; j < nums.length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                int l = j + 1, r = nums.length - 1, sum = -nums[i] - nums[j];
                while (l < r){
                    if (nums[l] + nums[r] == sum) {
                        ls.add(Arrays.asList(nums[i],nums[j], nums[l], nums[r]));
                        while (l < r && nums[l] == nums[l + 1]) l++;
                        while (l < r && nums[r] == nums[r - 1]) r--;
                        l++;
                        r--;
                    } else if (nums[l] + nums[r] < sum) {
                        while (l < r && nums[l] == nums[l + 1]) l++;   // 跳过重复值
                        l++;
                    } else {
                        while (l < r && nums[r] == nums[r - 1]) r--;
                        r--;
                    }
                }
            }
        }

        return ls;

时间复杂度 : O(N ^ 3)

空间复杂度 : O(1)