1.twosum.md

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]
 

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

https://leetcode-cn.com/problems/two-sum

相关企业

亚马逊 Amazon|128 字节跳动|58 谷歌 Google|56 微软 Microsoft|33 苹果 Apple|33

相关标签 Array Hash Table

相似题目 3Sum 中等

4Sum 中等

Two Sum II - Input Array Is Sorted 简单

Two Sum III - Data structure design 简单

Subarray Sum Equals K 中等

Two Sum IV - Input is a BST 简单

Two Sum Less Than K 简单

2 pointers structure

sort()
 
int left, right = 0, len-1
while(left<right){
    if (str[left] ... str[right]){
        left ++
    }else if (...){
        right --
    }else{
        return or record
    }
}

solution

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return [-1, -1]

        nums = [(number, index) for index, number in enumerate(nums)]

        nums = sorted(nums)

        left, right = 0, len(nums) - 1
        while left < right:
            if nums[left][0] + nums[right][0] > target:
                right -= 1
            elif nums[left][0] + nums[right][0] < target:
                left += 1
            else:
                return [ nums[left][1], nums[right][1] ]

        return [-1, -1]

class Solution {
    //two pointers alg
    public int[] twoSum(int[] nums, int target) {
        int[] result = {-1, -1};
        if (nums == null){
            return result;
        }
        
        //store all sorted paris
        Pair[] prs = new Pair[nums.length];
        for (int i = 0; i < nums.length; i++){
            Pair p = new Pair(nums[i], i);
            prs[i] = p;
        }
        Arrays.sort(prs);
        System.out.println(prs[0].number);
        
        //two pointer alg
        int left = 0; 
        int right = nums.length -1;
        while(left < right){
            if (prs[left].number + prs[right].number < target){
                left++;
            }else if (prs[left].number + prs[right].number > target){
                right--;
            }else{
                result[0] = prs[left].index;
                result[1] = prs[right].index;
                return result;
            }
        }
        
        return result;
    }
    
    class Pair implements Comparable<Pair>{
        int number;
        int index;
        
        public Pair(int number,int index){
            this.number = number;
            this.index = index;
        }
        
        public int compareTo(Pair other) {
            return number - other.number;
        }
    }
}