Leetcode solution - 01 Two Sum

Leetcode The first 01. Two Sum topic , questions Easy.

One . Subject requirements

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

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

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Two . Their thinking & Code implementation

There are three solutions to this problem

1. Brute force

We can see the pairwise combination of all array elements , Find the index of the combination that meets the condition , Feasible but slow , No discussion here .

2. Array traversal

From 0 Elements start , Add it to the following elements in turn to see whether the conditions are met , If it is satisfied, the corresponding index is returned . In the worst case, we need to start from 0 Traversing n-1, The time complexity is 𝑛(𝑛−1)2, Performance is still very low .

3. HashMap The way

The final solution here is to adopt Space for time The way , The introduction of a HashMap Record the index and value in the array （index,value）, If the subsequent traversal Map Included value Satisfy ：target - value , Then the conditions are met , Just return the corresponding index , The code is as follows ：

class Solution {
    
    public int[] twoSum(int[] nums, int target) {
    

        int length = nums.length;
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i< length; i ++) {
    
            int num = nums[i];
            if (map.containsKey(target - num)) {
    
                return new int[]{
    map.get(target - num), i};
            }
            map.put(num, i);
        }
        return new int[]{
    0, 0};
    }
}

• Running results

Runtime: 1 ms, faster than 99.97% of Java online submissions for Two Sum.

---

Lao tie saw this and gave a wave of praise 、 Comment on 、 How about paying attention to Sanlian

I am a AhriJ Zou classmate , Front and rear ends 、 Applet 、DevOps Are engaged in the explosion of stack engineers . The blog is constantly updated , If you think it's good , Welcome to the old tiesanlian , If it's not good, you're welcome to correct , learn from each other , Common progress .