LeetCode

LeetCode-18-四数之和

Posted by 刘知安 on 2019-03-13
文章目录
  1. FourSum
  2. ThreeSum

真的是醉了，3数和搞定又来了个4数和，思路肯定就是把4数和转化为3数和问题。本来呢，我还想利用3数和中类似的一个技巧，快速break掉的，可是老是有重复结果，折磨死我了。。。算了，就直接这样吧。

主要思路：

  • 4转3,3转2
  • 双指针

FourSum

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.*;

public class FourSum18 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // 注意一下，List是一个接口，不能被实例化，需要用LinkedList
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        // 先对数组进行排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            // 避免结果list中因相邻两次i下标值相同而出现重复
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int threeTarget = target - nums[i];  // 后面三个数的目标和

            for (int j = i + 1; j < nums.length - 2; j++) {
                // 避免结果list中因相邻两次j下标值相同而出现重复
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;
                int twoTarget = threeTarget - nums[j]; // 再后面两个数的目标和
                // 双指针
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    if (nums[left] + nums[right] == twoTarget) {
                        List<Integer> newList = new LinkedList<Integer>();
                        newList.add(nums[i]);
                        newList.add(nums[j]);
                        newList.add(nums[left]);
                        newList.add(nums[right]);
                        result.add(newList);
                        // 避免结果list中因相邻两次left下标值相同而出现重复
                        while (++left < right && nums[left] == nums[left - 1]) {
                        }
                        // 避免结果list中因相邻两次right下标值相同而出现重复
                        while (left < --right && nums[right] == nums[right + 1]) {
                        }
                    } else if (nums[left] + nums[right] < twoTarget) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        int[] nums1 = {0, 0, 0, 0};
        int[] nums2 = {-3, -2, -1, 0, 0, 1, 2, 3};
        int[] nums3 = {-5, -4, -3, -2, -1, 0, 0, 1, 2, 3, 4, 5};
        int[] nums4 = {1, -2, -5, -4, -3, 3, 3, 5};
        int target = -11;
        FourSum18 fourSum18 = new FourSum18();
        List<List<Integer>> res = fourSum18.fourSum(nums4, target);
        for (int i = 0; i < res.size(); i++) {
            System.out.println();
            for (int j = 0; j < res.get(i).size(); j++)
                System.out.println(res.get(i).get(j));
        }
    }
}

ThreeSum

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
import java.util.List;
import java.util.LinkedList;
import java.util.Arrays;

class ThreeSum15 {
    public List<List<Integer>> threeSum(int[] nums) {
        // 注意一下，List是一个接口，不能被实例化，需要用LinkedList来帮忙
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        // 先对数组进行排序
        Arrays.sort(nums);
        int target = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            // 受到LeetCode twoSum的启发，先将第一个数视为target
            // 再在后面的数中，找有没有满足条件的即可。
            target = nums[i];
            if (target > 0)   // 若当前数字大于0，那么后面肯定也都大于0，则不可能满足
                break;
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            // 设置两个移动的“指针”，分别指向两端。
            // 如果两数之和小于-target，就左指针右移；如果两数之和大于target，就右指针左移。
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] == -target) {
                    List<Integer> newList = new LinkedList<Integer>();
                    newList.add(nums[i]);
                    newList.add(nums[left]);
                    newList.add(nums[right]);
                    result.add(newList);
                    while (++left < right && nums[left] == nums[left - 1]) {
                    }
                    while (left < --right && nums[right] == nums[right + 1]) {
                    }
                } else if (nums[left] + nums[right] < -target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
}
FEATURED TAGS
LeetCode
FRIENDS