This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

The sum of two Numbers

Given an integer array nums and an integer target value target, find the two integers in the array and the target values and return their array subscripts. You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer. You can return the answers in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9 output: [0,1]Copy the code

Example 2:

Input: nums = [3,2,4], target = 6Copy the code

Example 3:

Input: nums = [3,3], target = 6Copy the code

Thought analysis

The easiest way to think of is brute force cracking, with two for loops, O(n2){O(n^2)}O(n2). O(n){O(n)}O(n), we can use a map to store the values in the array, key corresponds to nums[I], value corresponds to I, Check whether the target-nums [I] value exists in the map, if so, return the corresponding two positions in the array. The time complexity of the solution is O(n){O(n)}O(n), and the space complexity is also O(n){O(n)}O(n).

And there’s a solution to sort + double pointer, to sort the array first, before ordering copies a number of groups, and then prioritize, array sorted using double Pointers to find corresponding to the number of indices, for a sort has been made, so the array position has changed, so you need to copy the array traversal search index.

The code shown

Solution 1: Brute force cracking, time complexity O(n2){O(n^2)}O(n2), space complexity O(1)O(1)O(1) O(1).

public int[] twoSum(int[] nums, int target) {
        int length = nums.length;
        for(int i = 0; i < length; ++i){int outArrayValue = nums[i];
            for(int j = 0; j < length; ++j){if(outArrayValue + nums[j] == target && i ! = j){return new int[]{i,j}; }}}return null;
}
Copy the code

Solution 2: Use map to store traversed values for judgment. Time complexity O(n){O(n)}O(n), space complexity O(n)O(n)O(n) O(n).

    public int[] twoSum(int[] nums, int target) {
        
        int length = nums.length;
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < length; ++i){int value = target - nums[i];
            if(map.containsKey(value)){
                return new int[]{map.get(value),i};
            }
            map.put(nums[i],i);
        }
        return null;
     }
Copy the code

Solution three: sort + double pointer, time complexity O(logn){O(logn)}O(logn), space complexity O(n)O(n)O(n) O(n). This is the most complicated way to write it.

   public int[] twoSum(int[] nums, int target) {
   
    		int[] tempArray = Arrays.copyOf(nums,nums.length);
        int length = nums.length;
        int head = 0;
        int tail = length - 1;
        quickSort(nums, length);

        int[] targetArray = null;
        while (head < tail) {
            if (nums[head] + nums[tail] > target) {
                tail--;
            } else if (nums[head] + nums[tail] < target) {
                head++;
            } else {
                targetArray = new int[]{head, tail};
                break; }}int count = 0;
        boolean firstHasValue = false;
        boolean secondHasValue = false;
        for (int i = 0; i < length; i++){if (nums[targetArray[0]] == tempArray[i] && ! firstHasValue){ targetArray[0] = i;
                count++;
                firstHasValue = true;
                if (count == 2) {return targetArray;
                }
                continue;
            }
        
            if (nums[targetArray[1]] == tempArray[i] && ! secondHasValue){ targetArray[1] = i;
                count++;
                secondHasValue = true;
            }
            if (count == 2) {returntargetArray; }}return null;
    }


    private void quickSort(int[] nums,int n){
        quickInternal(nums,0,n - 1);
    }

    private void quickInternal(int[] nums,int l,int r){
        if(l >= r){
            return;
        }
        int division = partition(nums,l,r);
        quickInternal(nums,l,division - 1);
        quickInternal(nums,division + 1,r);
    }

    private int partition(int[] a,int l,int r){
        int base = a[l];
        while(l < r){
            
            while(l < r && a[r] >= base){
                r--;
            }
            a[l] = a[r];

            while(l < r && a[l] <= base){
                l++;
            }
            a[r] = a[l];
        }
        a[l] = base;
        return l;
    }
Copy the code

First, sort the array by quick sorting, then find the appropriate subscript by using the double pointer, and finally traverse the original array (that is, the copied array) to find the original subscript position, especially when finding the corresponding subscript position in the last step.

conclusion

The three solutions of the sum of two numbers, brute force cracking is the easiest but the time complexity is the highest. The solution using hash table has the best time complexity but needs O(n){O(n)}O(n) space, while the time complexity of double pointer + quicksort is O(logn){O(logn)}O(logn), The space complexity is not low O(n){O(n)}O(n), and the writing method is also more complicated.