题目

给定一个整数数列，找出其中和为特定值的那两个数。

你可以假设每个输入都只会有一种答案，同样的元素不能被重用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

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:

1
2
3

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

解题方法

嵌套循环

这个是一看到题目就会跳出来的想法，不需要思考，时间复杂度为O(n*n)，但是居然也A过了，毕竟是第一道简单级别的题，执行时间51ms。

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

利用排序

上面的方法虽然能过，但显然不是最优的方法，尝试先排序将复杂度降到O(nlogn)，然后利用双指针，前后逼近找到结果，然后再到原数组中定位这两个数，输出它们的indeces。这种方法执行时间为5ms，仅仅是上一个方法耗时的1/10，优化效果非常显著！

// Method_02
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Sort the array with QuickSort
        int[] result = new int[2];
        int[] sortedArray = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sortedArray);

        // Find two numbers
        int start = 0, end = sortedArray.length - 1;
        while (start < end) {
            while (sortedArray[start] + sortedArray[end] > target)
                end--;
            if (sortedArray[start] + sortedArray[end] == target)
                break;
            while (sortedArray[start] + sortedArray[end] < target)
                start++;
            if (sortedArray[start] + sortedArray[end] == target)
                break;
        }

        // Find their indices
        int flag = 0;
        int a = sortedArray[start], b = sortedArray[end];
        for (int i = 0; i < nums.length; i++)
            if (nums[i] == a || nums[i] == b)
                result[flag++] = i;

        return result;
    }
}

结语

这是笔者刷leetcode的开始，代码都托管在我的Github上，有兴趣的朋友可以相互交流，请多多指教。