算法日记-LeetCode-18.四数之和

2023-07-15

字数统计: 623字 | 阅读时长≈ 3分

算法日记-LeetCode-18.四数之和

原题链接：18. 四数之和 - 力扣（LeetCode）

题目大意

给定一个无序数组nums，以及目标值target，请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]

0 <= a < b < c< d < n
nums[a] + nums[b] + nums[c] + nums[d] = target

解题思路

循环

最直接的解决方法就是通过四重循环，但是四重循环的时间复杂度高，会超时

排序 + 双指针

四数之和与三数之和类型，可以通过，排序+双指针的方式，减少一重循环

对数组进行排序，然后通过两重循环确定nums[a]，nums[b]

随后借助双指针left和right确定nums[c]和nums[d]

sum = nums[left] + nums[right]

nums[a] + nums[b] + sum == target 满足条件
nums[a] + nums[b] + sum > target 右指针左移
nums[a] + nums[b] + sum < target 左指针右移

代码如下

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> list = new ArrayList<>();
        for (int a = 0; a < n - 3; a++) {
            if (a > 0 && nums[a] == nums[a - 1]) continue;
            for (int b = a + 1; b < n - 2; b ++) {
                if (b > a + 1 && nums[b] == nums[b - 1]) continue;
                int left = b + 1, right = n - 1;
                while (left < right) {
                    long sum = nums[left] + nums[right]; // long 型防止溢出
                    if (nums[a] + nums[b] == target - sum) {
                        List<Integer> ans = new ArrayList<>(Arrays.asList(nums[a], nums[b], nums[left], nums[right]));
                        list.add(ans);
                        while(left < right && nums[left] == nums[left + 1]) left++;
                        while(right > left && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (nums[a] + nums[b] > target - sum) {
                        right--;
                    } else if (nums[a] + nums[b] < target - sum){
                        left++;
                    }
                }
            }
        }
        return list;
    }
}

0ms 范例

import java.util.*;
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        return new AbstractList<List<Integer>>() {
            List<List<Integer>> list = null;

            public List<Integer> get(int index) {
                init();
                return list.get(index);
            }

            public int size() {
                init();
                return list.size();
            }

            private void init() {
                if (list != null) {
                    return;
                }
                final Set<List<Integer>> listSet = new HashSet<>();
                Arrays.sort(nums);
                for (int i = 0; i < nums.length - 3; i++) {
            for (int j = nums.length - 1; j > i + 2; j--) {
                int l = i + 1;
                int r = j - 1;
                while (l < r) {
                    long m = (long) nums[i] + (long) nums[j] + (long) nums[l] + (long) nums[r];
                    if (m ==  target) {
                        listSet.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        l++;
                        r--;
                    } else if (m > target) {
                        r--;
                    } else {
                        l++;
                    }
                }
            }
        }
                list = new ArrayList<>(listSet);
            }

        };
    }
}

本文作者： Naskete
本文链接： https://Naskete.github.io/2023/07/15/algorithm/算法日记-LeetCode-18.四数之和/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！