【LeetCode】two num·两数之和

题目描述

英文版描述

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.

英文版地址

leetcodehttps://leetcode.com/problems/two-sum/​leetcode.com/problems/two-sum/

中文版描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6

输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6

输出：[0,1]

提示

2 <= nums.length <= 104

-109 <= nums[i] <= 109

-109 <= target <= 109

只会存在一个有效答案

中文版地址

力扣https://leetcode.cn/problems/two-sum/

解题思路

遍历数组，每获取到一个值，再去遍历他后面的值，看是否有值等于目标值减去当前值

解题方法

俺这版

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for(int i=0; i<nums.length; i++){
            int cur = nums[i];
            int needed = target-cur;
            for(int j=(nums.length-1); j>i; j--){
                if(nums[j] == needed){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return result;
    }
}

官方版

查找表法

class Solution {
 public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>(nums.length);
        map.put(nums[0], 0);
        for(int i=1;i<nums.length;i++){
            int cur = nums[i];
            int needed = target - cur;
            if(map.containsKey(needed)){
                return new int[]{map.get(needed),i};
            }else{
                map.put(cur,i);
            }
        }
        throw new IllegalArgumentException("Can not find!");
    }
}