Given an array of integers nums and a 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, you cannot reuse the same elements in this array.

Example:

Given nums = [2, 7, 11, 15], target = 9

Nums [0] + nums[1] = 2 + 7 = 9

Method 1:

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

Complexity analysis:

Time complexity: O(n^2)O(n2), for each element, we try to find its corresponding target element by traversing the rest of the number set, which will take O(n)O(n) time. So the time is O(n^2)O(n2).

Space complexity: O(1)O(1).

Method 2:

class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); }}Copy the code

Complexity analysis:

Time complexity: O(n)O(n), we traversed the list containing NN elements only once. Each lookup in the table takes only O(1)O(1) time.

Space complexity: O(n)O(n), the additional space required depends on the number of elements stored in the hash table, which needs to store up to NN elements.

Boolean containsKey(Object obj) Checks whether a key exists in the map. Returns true if it does