java twoSum 算法：如何改进？

twoSum Algorithm : How to improve this?

提问by SuperMan

I felt like doing an algorithm and found this problem on leetcode

感觉自己在做一个算法，在leetcode上发现了这个问题

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

给定一个整数数组，找到两个数字，使它们相加为特定的目标数字。

函数 twoSum 应该返回两个数字的索引，使它们相加为目标，其中 index1 必须小于 index2。请注意，您返回的答案（index1 和 index2）不是从零开始的。

您可以假设每个输入都只有一个解决方案。

输入：数字={2, 7, 11, 15}，目标=9

输出：index1=1，index2=2

My solution is O(n^2). I wanted to know if there is better way of doing this? like O(n) or O(nlogn)

我的解决方案是 O(n^2)。我想知道是否有更好的方法来做到这一点？像 O(n) 或 O(nlogn)

import java.util.Arrays;
public class ReturnIndex {
    public int[] twoSum(int[] numbers, int target) {
        int tail = numbers.length-1;
        int[] n = new int[2];
        for (int i=0;i<tail;i++) {
            for(int j=i+1;j<tail;j++) {
                if(target ==(numbers[i]+numbers[j])) {
                    n[0] = i+1;
                    n[1] = j+1;
                }
            }
        }
        return n;
    }

    public static void main(String[] args) {
        int[] s = {150,24,79,50,88,345,3};
        int value = 200;
        ReturnIndex r = new ReturnIndex();
        int[] a = r.twoSum(s,value);
        System.out.println(Arrays.toString(a));
    }
}

采纳答案by Jeff Bowman

O(n log n)time, O(1)memory (not counting the list):

O(n log n)时间，O(1)内存（不包括列表）：

1. First, sort the list. This should take O(n log n)time, as most sort functions do.

2. Iterate through the list, which should take O(n)time in the outer loop. At this point you can do a binary search for the closest matching integer in a sorted sublist, which should take O(log n)time. This stage should wind up taking O(n log n)total.

1. 首先，对列表进行排序。这应该需要O(n log n)时间，就像大多数排序函数一样。

2. 遍历列表，这应该O(n)在外循环中花费时间。此时，您可以对排序的子列表中最接近的匹配整数进行二分搜索，这需要O(log n)时间。这个阶段应该结束O(n log n)。

Edit:Check out Max's answer below. It's still O(n log n) time and O(1) memory, but he avoids the binary searches by walking a pointer from each end of the list.

编辑：查看下面 Max 的回答。它仍然是 O(n log n) 时间和 O(1) 内存，但他通过从列表的每一端遍历一个指针来避免二进制搜索。

O(n)time, O(n)memory:

O(n)时间、O(n)记忆：

Build a hash table, which should have O(1)insertion and O(1)contains. Then, in a O(n)outer loop, for each number i, check if total - iis in the hash table. If not, add it; if so, then you've got your two numbers.

建立一个哈希表，它应该有O(1)插入和O(1)包含。然后，O(n)在外循环中，对于每个数字i，检查是否total - i在哈希表中。如果没有，添加它；如果是这样，那么你就有了你的两个号码。

Either way, you would need an additional scan through the array to get the indices, but that's no problem--it only takes O(n)time. If you wanted to avoid it you could keep the original index in the sorted list or hash table as needed, but that has a memory footprint instead of a time footprint.

无论哪种方式，您都需要对数组进行额外扫描以获取索引，但这没有问题——它只需要O(n)时间。如果您想避免它，您可以根据需要将原始索引保留在排序列表或哈希表中，但这会占用内存而不是时间占用。

回答by Max

Sort the array. Make two pointers point at first and last (x and X). Run this in a loop:

对数组进行排序。使两个指针指向第一个和最后一个（x 和 X）。循环运行：

if      (a[X]+a[x] >  N) then X-- 
else if (a[X]+a[x] <  N) then x++
else if (a[X]+a[x] == N) then found.

if (x > X) then no numbers exist.

O(nlogn)time, O(1)memory

O(nlogn)时间，O(1)记忆

回答by RGO

Below you can find a solution in which the two numbers could be found in O(n log n)time:

您可以在下面找到可以及时找到这两个数字的解决方案O(n log n)：

1- Sort the numbers in ascending (or descending) order             // O(n log n)

2- Compute diff = target - item for each item                      // O(n) 

3- For each calculated diff, look up the calculated value in the sorted items 
   using the Binary search algorithm                               // O(n log n) 

A complete, working implementation in Java:

一个完整的 Java 实现：

import java.util.ArrayList;

public class NumbersFinder {

    class Item{
        private int value;
        private int index;

        public Item(int value, int index){
            this.value = value;
            this.index = index;
        }

        public int getValue(){
            return value;
        }

        public int getIndex(){
            return index;
        }
    }

    public ArrayList<Item> find(int[] values, int target){      
        ArrayList<Item> items = new ArrayList<Item>();
        for(int i = 0; i < values.length; i++)
            items.add(new Item(values[i], i));

        items = quicksort(items);
        ArrayList<Integer> diffs = computeDiffs(items, target);

        Item item1 = null;
        Item item2 = null;

        boolean found = false;

        for(int i = 0; i < diffs.get(i) && !found; i++){
            item1 = items.get(i);
            item2 = searchSortedItems(items, diffs.get(i), 0, items.size());
            found = item2 != null;
        }
        if(found){
            ArrayList<Item> result = new ArrayList<Item>();
            result.add(item1);
            result.add(item2);
            return result;
        }
        else
            return null;
    }

    // find "value" in the sorted array of "items" using Binary search in O(log n)
    private Item searchSortedItems(ArrayList<Item> items, Integer value, int lower, int upper) {
        if(lower > upper)
            return null;
        int middle = (lower + upper)/2;
        Item middleItem = items.get(middle);
        if(middleItem.getValue() == value)
            return middleItem;
        else if(middleItem.getValue() < value)
            return searchSortedItems(items, value, middle+1, upper);
        else
            return searchSortedItems(items, value, lower, middle-1);
    }

    // Simply calculates difference between the target value and each item in the array; O(n)
    private ArrayList<Integer> computeDiffs(ArrayList<Item> items, int target) {
        ArrayList<Integer> diffs = new ArrayList<Integer>();
        for(int i = 0; i < items.size(); i++)
            diffs.add(target - items.get(i).getValue());
        return diffs;
    }

    // Sorts items using QuickSort algorithm in O(n Log n)
    private ArrayList<Item> quicksort(ArrayList<Item> items) {
        if (items.size() <= 1)
            return items;
        int pivot = items.size() / 2;
        ArrayList<Item> lesser = new ArrayList<Item>();
        ArrayList<Item> greater = new ArrayList<Item>();
        int sameAsPivot = 0;
        for (Item item : items) {
            if (item.getValue() > items.get(pivot).getValue())
                greater.add(item);
            else if (item.getValue() < items.get(pivot).getValue())
                lesser.add(item);
            else
                sameAsPivot++;
        }
        lesser = quicksort(lesser);
        for (int i = 0; i < sameAsPivot; i++)
            lesser.add(items.get(pivot));
        greater = quicksort(greater);
        ArrayList<Item> sorted = new ArrayList<Item>();
        for (Item item : lesser)
            sorted.add(item);
        for (Item item: greater)
            sorted.add(item);
        return sorted;
    }


    public static void main(String[] args){
        int[] s = {150,24,79,50,88,345,3};
        int value = 200;

        NumbersFinder finder = new NumbersFinder();
        ArrayList<Item> numbers = finder.find(s, value);

        if(numbers != null){
            System.out.println("First Number Found = " + numbers.get(0).getValue() + " ; Index = " + + numbers.get(0).getIndex());
            System.out.println("Second Number Found = " + numbers.get(1).getValue() + " ; Index = " + + numbers.get(1).getIndex());
        }
        else{
            System.out.println("No such two numbers found in the array!");
        }
    }
}

Output:

输出：

First Number Found = 50 ; Index = 3
Second Number Found = 150 ; Index = 0

回答by Extreme

As @Prayer mentioned above, here is the accepted answer.

正如上面提到的@Prayer，这是公认的答案。

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

回答by Zstack

I tried most of the answers and they don't seem to handle the edge cases properly. Hence, throwing my two cents for python3 solution that handles the edge cases. I used Max's algorithm to implement it:

我尝试了大部分答案，但他们似乎没有正确处理边缘情况。因此，为处理边缘情况的python3解决方案投入我的两分钱。我使用 Max 的算法来实现它：

   def twoSum(nums, target):
    output=[]
    arr=sorted(nums)
    x=0
    y=-1
    X=len(nums)-1
    while x<X:
        if (arr[X]+arr[x] >  target):
            X-=1 
        elif (arr[X]+arr[x] <  target):
            x+=1
        elif (arr[X]+arr[x] == target):
            #print("Found",arr[X],arr[x])
            num1=arr[x]
            num2=arr[X]
            x+=1
            X-=1 
    for i in range(len(nums)):
        if num1 == nums[i] and y==-1:
            index1=i
            y=i
        elif num2 == nums[i]:
            index2=i         
    return [index1, index2]

N.B. It's important to consider edge cases and inputs like the following

NB 考虑如下边缘情况和输入很重要

print(twoSum([3,2,4],  6)) # [1,2]
print(twoSum([3,3],  6))  # [0,1]

回答by Marc Carré

The na?ve solution to the two-sum problem is O(n^2), s.t. nis the length of the array of numbers provided.

二和问题的简单解是O(n^2)，stn是提供的数字数组的长度。

However, we can do better by using a hash-map of the values seen so far (key=number, value=index) and checking if the complement is already there (O(1)) as we iterate over the numbers. This approach is optimal for an unsorted array:

然而，我们可以通过使用迄今为止看到的值的哈希映射（key=number，value=index）并O(1)在我们迭代数字时检查补码是否已经存在（）来做得更好。这种方法最适合未排序的数组：

• Runtime complexity: O(n)
• Space complexity: O(n)-- though if there is a solution, in practice this would be O(n/2)

• 运行时复杂度： O(n)
• 空间复杂度：O(n)--尽管如果有解决方案，在实践中这将是O(n/2)

Given the OP's question:

鉴于OP的问题：

• does notspecify whether the input array is sorted or not (it is, therefore, safe to assume the input array can be anything), and
• specifically asks for indexesof the provided array, as opposed to the actual numbers, any kind of solution sorting the array would need to copy it beforehand, keep a mapping of indexes between the sorted array and the unsorted one, or iterate over the original array, hence costing memory (O(n)) or time (O(n)), depending on the approach chosen. Therefore, the 1st part of the (currently) accepted solutionis, strictly speaking, incorrect.

• 并没有指定输入阵列是否被排序或不（它是，因此，安全地假定输入数组可以是任何东西），和
• 特别要求提供的数组的索引，而不是实际的数字，任何对数组进行排序的解决方案都需要事先复制它，在已排序数组和未排序数组之间保留索引的映射，或迭代原始数组，因此会消耗内存 ( O(n)) 或时间 ( O(n))，具体取决于所选择的方法。因此，（当前）接受的解决方案的第一部分严格来说是不正确的。

Optimal solution:

最优解：

• In Python:

• 在 Python 中：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for j, num in enumerate(nums):
            i = seen.get(target-num, -1)
            if i != -1:
                return [i+1, j+1]
            seen[num] = j
        return [-1, -1]

• In Java:

• 在 Java 中：

import java.util.Map;
import java.util.HashMap;

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        final Map<Integer, Integer> seen = new HashMap<>();
        for (int j = 0; j < nums.length; ++j) {
            final Integer i = seen.get(target - nums[j]); // One hash-map access v.s. two when using contains beforehand.
            if (i != null) {
                return new int[]{ i+1, j+1 };
            }
            numbers.put(nums[j], j);
        }
        return new int[]{-1, -1};
    }
}

Note that by construction, if the complement is present in the map/dictionary, then the index stored will always be lower than the current index. Hence the following proposition is verified:

请注意，通过构造，如果地图/字典中存在补码，则存储的索引将始终低于当前索引。因此以下命题得到验证：

index1 must be less than index2

index1 必须小于 index2

Also note that the OP's question needed 1-based indexes, which is what I've provided above, but the Leetcode question referred to seems to have been updated since then, and now is 0-based: https://leetcode.com/problems/two-sum.

另请注意，OP 的问题需要基于 1 的索引，这是我在上面提供的索引，但所提到的 Leetcode 问题似乎从那时起已更新，现在是基于 0 的：https://leetcode.com/问题/二和。

I hope this helps.

我希望这有帮助。

回答by Abhay

Here is an Efficient Solution.

这是一个有效的解决方案。

Time Complexity - O(n)and Space Complexity - O(1)

时间复杂度 - O(n)和空间复杂度 - O(1)

Sol: Will take two-pointer(start_pointer and end_pointer). Initially start_pointer point at the first index and end_pointer point to the last.

Sol：将采用两个指针（start_pointer 和 end_pointer）。最初 start_pointer 指向第一个索引，end_pointer 指向最后一个。

Add both the element (sum = array[start_pointer] + array[last_pointer]. After that check, if the sum > targetelement or not. If yes decrease the end_pointerelse increase start_pointer. If sum = target, means you got the indexes.

添加两个元素（sum = array[start_pointer] + array[last_pointer]。在那之后检查，如果sum > targetelement or not。如果是，减少end_pointer否则增加start_pointer。如果sum = target，意味着你得到了索引。

public int[] twoSum(int[] numbers, int target) {

    int[] arr = new int[2]; // to store result
    int sum=0;

    int start_pointer=0;     
    int end_pointer = (numbers.length)-1;

    while(start_pointer<=end_pointer){

        sum=numbers[start_pointer]+numbers[end_pointer]; 

        if(sum>target)
            end_pointer-=1;
        else if(sum<target)
            start_pointer+=1;
        else{
            arr[0]=start_pointer;
            arr[1]=end_pointer;
            break;
        }       
    }       
    return arr;
}

回答by TejeshGangari

We can do with HashMap and the time complexity would be O(n)

我们可以使用 HashMap 并且时间复杂度为 O(n)

public class ReturnIndicesOfElementsAddToSum {

public static void main(String[] args) {
    int[] nums = {2, 7, 11, 15};
    int target = 18;

    if(!getIndices(nums,target)) {
        System.out.println("No such numbers found");
    }

}

static boolean getIndices(int[] nums, int target) {
    Map<Integer,Integer> indexMap = new HashMap<>();
    boolean numFound = false;
    for(int i=0;i<nums.length;i++) {
        int temp = target - nums[i];
        indexMap.put(nums[i], i);
        if(indexMap.containsKey(temp)) {
            System.out.printf("%d and %d adds upto the target value and indices are %d and %d"
                            , nums[i], temp, i, indexMap.get(temp));
            numFound = true;
        }
    }
    return numFound;
}

}

}

回答by Lolo

I would approach it this way:

我会这样处理：

1. Order your array from smaller to lower value

2. Loop over your array the way you have it but exit the loop early whenever

   target <(numbers[i]+numbers[j])

3. Once you have the value of your two elements such that n[0] + n[1] = target, look back at the original array to find their index.

1. 将数组从小到低排序

2. 以您拥有的方式循环遍历您的数组，但只要提前退出循环

   目标 <(数字[i]+数字[j])

3. 一旦您获得了两个元素的值，使得 n[0] + n[1] = 目标，请查看原始数组以找到它们的索引。

回答by fandyst

One line solution in python :

python中的一行解决方案：

class Solution(object):
    """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
    """
    def twoSum(self, nums, target):            
        x = [[i, nums.index(target-j)] for i,j in enumerate(nums) if nums.count(target-j) > 0 and nums.index(target-j)!=i]

        return x.pop()