1. Sum of two numbers

Difficulty is simple

Given an integer array nums and an integer target value target, find the two integers in the array and the target value target 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

Tip:

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

Advanced: Can you think of an algorithm whose time complexity is less than O(n2)?

Answer key

The simplest solution to this problem would be the two-level for loop violence solution, but you have to think about how to optimize it. The official solution uses HashMap, which is a quick lookup of complementary (loosely) terms. So how do we use complementary terms? Let’s take an example to understand:

Input: nums = [2,7,11,15], target = 9

  • When I is equal to 0

    Target (9) -2 = 7, now that HashMap does not store any ordered pairs, store nums[0] = 2 and its ordered pair <2,0> of subscript 0 into HashMap

  • When I is equal to 1

    If (hashtable.containsKey(temp)), if(hashtable.containsKey(temp)), New int[]{hashtable.get(target-nums [I]), I}; Plus the current I =1 returns {0,1}

class Solution { public int[] twoSum(int[] nums, int target) { int n = nums.length; // Array length Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>(n-1); For (int I = 0; int I = 0; i < n; i++){ int temp = target - nums[i]; If (hashtable.containskey (temp)){// If (hashtable.containskey (temp)){// If (hashtable.containskey (temp)){// Return new int[]{hashtable.get(target-nums [I]), I}; } hashtable.put(nums[I], I); // Get (target-nums [I]); <nums[I], I > map} return new int[0]; }}Copy the code