LeetCode 1. Sum of two numbers

Title Description ： Given an array of integers nums And an integer target value target, Please find... In the array And is the target value target the Two Integers , And return their array subscripts .

You can assume that each input corresponds to only one answer . 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]
 explain ： because  nums[0] + nums[1] == 9 , return  [0, 1] .

Example 2：

 Input ：nums = [3,2,4], target = 6
 Output ：[1,2]

Example 3：

 Input ：nums = [3,3], target = 6
 Output ：[0,1]

Tips ：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
 There will only be one valid answer 

Advanced ： You can come up with a time complexity less than O(n2) The algorithm of ？

Method 1 ： Brute force

  public static int[] twoSum1(int[] nums, int target){
    
        int[] rs = new int[2];
        for(int i = 0; i < nums.length-1; i++){
    
            for(int j = i+1; j < nums.length; j++){
    
                if(nums[i] + nums[j] == target){
    
                    rs[0] = i;
                    rs[1] = j;
                    return rs;
                }
            }
        }

        return rs;
    }

Method 1 ： Use Map aggregate

1. First declare a Map aggregate , among key Storage nums[i] Value , value Storage nums[i] The subscript i.
2. Traverse nums Array , Judge target - nums[i] Whether there is map Collection ：
   If not map Collection , Just put <nums[i], i> Deposit in map Collection ;
   If in map Collection , that map.get(target - nums[i]) and i Is a set of subscripts required for this question .

 public static int[] twoSum(int[] nums, int target){
    
        int[] rs = new int[2];
        if(nums == null || nums.length == 0){
    
            return rs;
        }

        //  Make a statement map aggregate 
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
    
            int temp = nums[i];
            if(map.containsKey(target - temp)){
    
                rs[0] = map.get(target - temp);
                rs[1] = i;
                return rs;
            }

            map.put(temp, i);
        }
        return rs;
    }

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/two-sum
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .