1.Two Sum(Easy)
LanyuanXiaoyao's Blog ヽ(✿゚▽゚)ノ

1.Two Sum(Easy)

2016-10-05

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. 给定一个整数数组,返回两个数的下标,使这两个数的和等于指定的目标数,假定每个输入的数组都有恰好一个解

Example:

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

My Solution

(Java) Version 1 Time: 98ms:

  在数组中从前往后搜索,每一个数都和其余的数进行求和判断,如果有结果则直接输出,题目中已经假设只有一个解,不需要再向后搜索

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++)
            for (int j = 0; j < nums.length; j++) {
                if (i == j)
                    continue;
                if (nums[i] + nums[j] == target)
                    return new int[] { i, j };
            }
        return nums;
    }
}

(Java) Version 2 Time: 52ms:

  对上一个算法的改进在于,第一次循环搜索的数之前的数不需要再在第二个循环重新判断一次,每一次循环都只需要和后面的数作比较,前面的数在上一次循环中已经被比较过一次了,同时,因为不需要同前面的数进行比较,那么,比较可以跳过自己,直接从i+1开始,省去了判断i==j的步骤

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

(Java) Version 3 Time: 8ms (By plover):

  运用Java的Map,构造Map键为当前判断的数的期望目标数,值为数的下标,通过搜索键来判断是否存在对应的期望目标数,并可以快速找到其下标,不需要重新循环一次。巧妙应用Map把数组中的数和下标绑定在一起,达到快速获得数及其下标的目的

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> pair=new HashMap<>();
        int result[] = new int[2];
        for(int i=0;i<nums.length;i++){
            if(pair.containsKey(nums[i])){
                result[0]=pair.get(nums[i]);
                result[1]=i;
                return result;
            }
            else{
                pair.put(target-nums[i], i);
            }
        }
    return result;
    }
}

评论