題目描述

思路

分兩種：排序之后從兩邊向中間遍歷赐稽；哈希表

排序

為了能夠排完序之后保留下標(biāo)信息，需要新定義一個類浑侥。在類中保留數(shù)字和對應(yīng)下標(biāo)姊舵，并實(shí)現(xiàn)Compareble接口，重寫compareTo方法寓落，注意在compareTo方法中只對數(shù)字進(jìn)行比較括丁，而下標(biāo)不參與比較。我把這個類定義為Data伶选。

定義完這個類之后史飞，由所給數(shù)組（nums）新建一個Data數(shù)組尖昏。然后調(diào)用Arrays.sort()對Data數(shù)組進(jìn)行排序。從數(shù)組的兩端（頭指針pre祸憋，尾指針post）向中間逼近会宪，尋找加和等于target的兩個數(shù)。

在尋找的過程中蚯窥，若pre和post指向的兩個數(shù)相加小于target掸鹅，則pre加1；若大于target拦赠，則post-1巍沙；若等于target，退出循環(huán)并返回結(jié)果荷鼠。

java代碼如下：

import java.util.Arrays;

class Solution {
    public class Data implements Comparable {
        int index;
        int data;

        Data(int index, int data) {
            this.data = data;
            this.index = index;
        }

        @Override
        public int compareTo(Object o) {
            if (o instanceof Data) {
                Data s = (Data) o;
                if (this.data > s.data)
                    return 1;
                else if (this.data == s.data)
                    return 0;
                else
                    return -1;
            }
            return 0;
        }
    }

    public int[] twoSum(int[] nums, int target) {
        int length = nums.length;
        int pre = 0;
        int post = length - 1;
        int sum = 0;

        Data[] datas = new Data[length];
        for (int i = 0; i < length; i++)
            datas[i] = new Data(i, nums[i]);

        Arrays.sort(datas);

        while (true) {
            sum = datas[pre].data + datas[post].data;
            if (sum == target) {
                break;
            } else if (sum < target) {
                pre = pre + 1;
            } else {
                post = post - 1;
            }
        }

        int[] res = { datas[pre].index, datas[post].index };
        return res;
    }
}

執(zhí)行用時：6 ms, 在所有 Java 提交中擊敗了36.96%的用戶
內(nèi)存消耗：38.7 MB, 在所有 Java 提交中擊敗了32.34%的用戶

36%句携，結(jié)果不太好，下一個方法允乐。

哈希表

以數(shù)組下標(biāo)為key矮嫉，對應(yīng)位置上的元素為value，創(chuàng)建hashMap牍疏，命名為map蠢笋。

對所給數(shù)組nums進(jìn)行遍歷。對每個元素鳞陨，若與該元素加和為target的那個數(shù)是map的一個key昨寞，則找到答案，將該元素的下標(biāo)與那個key對應(yīng)的value返回厦滤；若不是map的一個key援岩，將該元素的<元素值，下標(biāo)>添加到map中（即使該元素已存在與map中也無所謂掏导，因?yàn)轭}設(shè)已說明答案必定唯一）

一次遍歷即可得到結(jié)果

java代碼如下：

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int length = nums.length;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

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

        return null;
    }
}

執(zhí)行用時：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶
內(nèi)存消耗：38.7 MB, 在所有 Java 提交中擊敗了41.46%的用戶