[LeetCode the sum of two Numbers II] | punch brush

Has been the habit of brush, recently saw the nuggets held a brush activities, especially to participate in! This is the second question submitted this time.

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

I. Title Description:

Describe a set of integers and ask how many pairs of integers can be found whose sum is greater than a given target value. Please return your answer. Example Example 1:

Input: [2, 7, 11, 15], target = 24 Output: 1 Explanation: 11 + 15 is the only pairCopy the code

Example 2:

Input: [1, 1, 1, 1], target = 1 Output: 6Copy the code

challenge

O(1) extra space and O(nlogn) time complexity

Ii. Analysis of Ideas:

Iii. AC Code:

public class Solution {
    /**
     * fix bug :back conditons is 0
     * 
     * @param nums:   an array of integer
     * @param target: An integer
     * @return: an integer
     */
    public int twoSum2(int[] nums, int target) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int start = 0;
        int end = nums.length - 1;
        int count = 0;
        while (start < end) {
            if (nums[start] + nums[end] <= target) {
                start++;
            } else {
                // sum temp result
                intsize = end - start; count += size; end--; }}returncount; }}Copy the code

Iv. Summary:

Opposite double pointer, belong to a kind of double pointer, common terms sort, fight arena search, sum and so on

• Time complexity is O(nlogn)O(nlogn)O(nlogn) O(nlogn), in situ search space complexity is O(1)O(1)O(1) O(1)
• The disadvantage of dual Pointers is that they need to be sorted in advance, and the actual use of the process needs to consider whether the specific scenario allows sorting in advance