LeetCode 1. Sum of two numbers

I. Details of the subject

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:

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

Second, the train of thought

The first thing that comes to mind is a two-level loop, going through each combination in the set. Just like in probability theory, you take two integers out of N, as long as the sum of the two integers is target. This is certainly possible, but it takes time, order N ^ 2.

If a HashMap is used to store the index I and the value nums[I] for each element in the array, the result can be found by querying the HashMap based on target-nums[I] for each element in the array at level 1. The total time is order N.

Three, code,

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0; i<nums.length; i++) {int rest=target-nums[i];
          if(map.containsKey(rest)) {
            return new int[] {i,map.get(rest)};
          }
          map.put(nums[i], i); // place it after to prevent the same element from appearing twice.
        }
        throw new IllegalArgumentException("No two sum solution"); }}Copy the code