Topic link

Leetcode-cn.com/problems/tw…

Topic describes

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 = 9Copy the code

The problem solving scheme

Train of thought

  • Tag: Hash mapping
  • This problem itself is easily solved by traversal by force, in order n2.
  • Since the time complexity of hash lookup is O(1), the hash container map can be used to reduce the time complexity
  • The nums group is traversed. I is the current subscript, and each value determines whether the map existstarget-nums[i]The key value
  • If present, both values are found, if not, the current(nums[i],i)Save it to the map and keep iterating until you find it
  • An exception is thrown if there is no result
  • Time complexity: O(n)

code

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

Draw solution

Background reply “algorithm”, join every day algorithm group feel algorithm directly to the soul, welcome to click on and forward