Nuggets team number online, help you Offer impromptu! Click for details

The title

Given an array nums containing n integers and a target value target, determine whether there are four elements a, B, c, and D in nums such that a + b + C + D is equal to target. Find all quaternions that meet the condition and are not duplicated.

Train of thought

The sum of the four numbers is common to the sum of the previous three numbers and the sum of the two numbers, that is, the left boundary and the right boundary must be determined

Nums.length-1 = nums.length-1 = nums.length-1 = nums.length-1 = nums.length-1 = nums.length-1 = nums.length-1 = nums.length-1 = nums.length-1 = nums.length-1 = nums.length-1 = nums.length-1 = nums.length-1 = nums.length-1 = nums.length-1 = nums.length-1 = nums.length-1 = nums.length-1

If left is smaller than right, use left and right to approximate each other to obtain a matching array. After obtaining the array, determine whether nums[left] == nums[left+1] determines whether the value of the current element is equal to the value of the next element.

The problem solving

    public List<List<Integer>> fourSum(int[] nums, int target) {
        // Check if it is a valid array
        int size = nums.length;
        if (size < 4) {
            return Collections.emptyList();
        }
        / / sorting
        Arrays.sort(nums);
        // Define List to accept the result
        List<List<Integer>> lists = new ArrayList<>();
        // Outermost loop
        for (int a = 0; a < size; a++) {
            // If the leftmost number has moved to the right, check whether it is the same as the previous number, if so, break out of the loop (get the first number)
            if (a > 0 && nums[a] == nums[a - 1]) {
                continue;
            }
            // Add one to the first number.
            for (int b = a + 1; b < size; b++) {
                if (b > a + 1 && nums[b] == nums[b - 1]) {
                    continue;
                }
                // Define the third number.
                int left = b + 1;
                // Put the last number at the end of the array (get the fourth number)
                int right = size - 1;
                // If the left pointer is less than the right pointer, execute the loop
                while (left < right) {
                    // if the sum of four numbers is less than target, run left++ to make target larger
                    if (nums[a] + nums[b] + nums[left] + nums[right] < target) {
                        left++;
                        // if the sum of four terts is greater than target, execute right++ to make target smaller
                    } else if (nums[a] + nums[b] + nums[left] + nums[right] > target) {
                        right--;
                    } else {
                        // The sum of terts equals target in the list
                        lists.add(Arrays.asList(nums[a], nums[b], nums[left], nums[right]));

                        // Check whether the number left is moving right is equal to the current value, if so, execute left++
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        // Determine if right is equal to the current value, if so, execute right--
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        // left++ continue with the next exploration
                        left++;
                        // left++ continue with the next explorationright--; }}}}// Return the final result
        return lists;
    }
Copy the code

conclusion

With the experience of the sum of two and three numbers, the idea of solving this problem is relatively easy, but in the process of writing their own code, there will still be bugs, or some small details are not considered

Read the original