18 4Sum

痛定思痛。 2022-08-10 00:50 111阅读 0赞

类似的题目有  
[1 TwoSum][]  
[15 3Sum][]  
[16 3Sum Closest][]

第一次使用的是笨办法，四层嵌套for循环，总是超时

public static List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            Arrays.sort(nums);
    
            for (int a = 0; a < nums.length - 3; a++) {
                for (int b = a + 1; b < nums.length - 2; b++) {
                    for (int c = b + 1; c < nums.length - 1; c++) {
                        for (int d = c + 1; d < nums.length; d++) {
                            if ((nums[a] + nums[b] + nums[c] + nums[d]) == target) {
                                List<Integer> list = new ArrayList<Integer>();
                                list.add(nums[a]);
                                list.add(nums[b]);
                                list.add(nums[c]);
                                list.add(nums[d]);
                                if (!result.contains(list))
                                    result.add(list);
                            } else if ((nums[a] + nums[b] + nums[c] + nums[d]) < target)
                                continue;
                            else
                                break;
                        }
                    }
                }
            }
            return result;
        }

第二次使用的办法就没有超时

public static List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
    
            Arrays.sort(nums);
            for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    int k = j + 1;
                    int l = nums.length - 1;
    
                    while (k < l) {
                        int sum = nums[i] + nums[j] + nums[k] + nums[l];
                        if (sum > target) {
                            l--;
                        } else if (sum < target) {
                            k++;
                        } else {
                            List<Integer> list = new ArrayList<Integer>();
                            list.add(nums[i]);
                            list.add(nums[j]);
                            list.add(nums[k]);
                            list.add(nums[l]);
                            if (!result.contains(list))
                                result.add(list);
                            k++;
                            l--;
                        }
                    }
                }
            }
            return result;
        }

[1 TwoSum]: http://blog.csdn.net/taoxiuxia/article/details/46426585
[15 3Sum]: http://blog.csdn.net/taoxiuxia/article/details/49684621
[16 3Sum Closest]: http://blog.csdn.net/taoxiuxia/article/details/49686639