[LeetCode of the sum of two Numbers – different] | punch brush

Has been the habit of brush, recently saw the nuggets held a brush activities, especially to participate in! This is question 7. I have to say the nuggets theme is beautiful! Praise.

Although it is the seventh problem, but still belongs to the double pointer of the topic, see the double pointer have vomit, don’t worry, we will practice so far.

This article is participating in the nuggets team online activity, clickCheck spring recruitment positions in big factories

I. Title Description:

Sum of two numbers – different compositions

Given an array of integers, find how many pairs of different elements in the array have the same sum, and the sum is the given target value, return the logarithm.

Case 1:

Input: nums = [1,1,2,45,46,46] target = 47 Output: 2Copy the code

Example 2:

Input: nums = [1,1] target = 2 Output: 1 Interpretation: 1 + 1 = 2Copy the code

Ii. Analysis of Ideas:

methods	describe	Time complexity	Spatial complexity
Double pointer	Sort first, then double pointer	$O(N)$	$(N)$
Double pointer	Using temporary variablescountRecords in accordance withtargetNumber of combinations of	$O(N)$	$(N)$
Double pointer	Skip duplicate element values	$O(N)$	$(N)$

Iii. AC Code:

import java.util.Arrays;

public class TwoSum {

    public static void main(String[] args) {
        int[] nums = new int[] { 1.0, -1 };
        int target = 0;
        System.out.print(twoSum(nums, target));
    }

    public static int twoSum(int[] nums, int target) {
        // back conditions
        if (nums == null || nums.length < 2) {
            // why need < 2?
            return 0;
        }

        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        int count = 0;
        while (left < right) {
            int currentSum = nums[left] + nums[right];
            if (currentSum == target) {
                count++;
                left++;
                right--;
                while (left < right && nums[right] == nums[right + 1]) {
                    right--;
                }
                while (left < right && nums[left] == nums[left - 1]) { left++; }}else if (currentSum > target) {
                right--;
            } else{ left++; }}returncount; }}Copy the code

Iv. Summary:

Different from the previous two-pointer search, this problem needs to continue the search until the end of the process, using the count count, to record the result. Careful friends will ask, this question only test a count count is so simple? A: Of course not. Also consider the following:

1. Duplicate element filtering, how to skip the same elementnums[right]==nums[right+1]
2. Array out of bounds handling,left<right

The lesson of this problem is how to deal with the same elements, how to count different components.