Search unsorted array for 3 elements which sum to

问题:

I am trying to make an algorithm, of Θ( n² ).
It accepts an unsorted array of n elements, and an integer z,
and has to return 3 indices of 3 different elements a,b,c ; so a+b+c = z.
(return NILL if no such integers were found)

I tried to sort the array first, in two ways, and then to search the sorted array.
but since I need a specific running time for the rest of the algorithm, I am getting lost.
Is there any way to do it without sorting? (I guess it does have to be sorted) either with or without sorting would be good.

example:
for this array : 1, 3, 4, 2, 6, 7, 9 and the integer 6

It has to return: 0, 1, 3

because ( 1+3+2 = 6)

回答1:

Algorithm

1. Sort - O(nlogn)
2. for i=0... n-1 - O(1) assigning value to i
3. new_z = z-array[i] this value is updated each iteration. Now, search for new_z using two pointers, at begin (index 0) and end (index n-1) If sum (array[ptr_begin] + array[ptr_ens]) is greater then new_z, subtract 1 from the pointer at top. If smaller, add 1 to begin pointer. Otherwise return i, current positions of end and begin. - O(n)
4. jump to step 2 - O(1)

Steps 2, 3 and 4 cost O(n^2). Overall, O(n^2)

C++ code

#include <iostream>
#include <vector>
#include <algorithm>


int main()
{
    std::vector<int> vec = {3, 1, 4, 2, 9, 7, 6};
    std::sort(vec.begin(), vec.end());

    int z = 6;
    int no_success = 1;
    //std::for_each(vec.begin(), vec.end(), [](auto const &it) { std::cout << it << std::endl;});

    for (int i = 0; i < vec.size() && no_success; i++)
    {

        int begin_ptr = 0;
        int end_ptr = vec.size()-1;
        int new_z = z-vec[i];

        while (end_ptr > begin_ptr)
        {
            if(begin_ptr == i)
                begin_ptr++;
            if (end_ptr == i) 
                end_ptr--;

            if ((vec[begin_ptr] + vec[end_ptr]) > new_z)
                end_ptr--;
            else if ((vec[begin_ptr] + vec[end_ptr]) < new_z)
                begin_ptr++;
            else {
                std::cout << "indices are: " << end_ptr << ", " << begin_ptr << ", " << i << std::endl;
                no_success = 0;
                break;
            }
        }
    }
    return 0;
}

Beware, result is the sorted indices. You can maintain the original array, and then search for the values corresponding to the sorted array. (3 times O(n))

回答2:

The solution for the 3 elements which sum to a value (say v) can be done in O(n^2), where n is the length of the array, as follows:

1. Sort the given array. [ O(nlogn) ]

2. Fix the first element , say e1. (iterating from i = 0 to n - 1)

3. Now we have to find the sum of 2 elements sum to a value (v - e1) in range from i + 1 to n - 1. We can solve this sub-problem in O(n) time complexity using two pointers where left pointer will be pointing at i + 1 and right pointer will be pointing at n - 1 at the beginning. Now we will move our pointers either from left or right depending upon the total current sum is greater than or less than required sum.

So, overall time complexity of the solution will be O(n ^ 2).

Update:

I attached solution in c++ for the reference: (also, added comments to explain time complexity).

 vector<int> sumOfthreeElements(vector<int>& ar, int v) {
        sort(ar.begin(), ar.end());
        int n = ar.size();
        for(int i = 0; i < n - 2 ; ++i){ //outer loop runs `n` times
            //for every outer loop inner loops runs upto `n` times
            //therefore, overall time complexity is O(n^2).
            int lo = i + 1;
            int hi = n - 1;
            int required_sum = v - ar[i];
            while(lo < hi) {
                int current_sum = ar[lo] + ar[hi];
                if(current_sum == required_sum) {
                    return {i, lo, hi};
                } else if(current_sum > required_sum){
                     hi--;
                }else lo++;
            }
        }
        return {};
    }

回答3:

I guess this is similar to LeetCode 15 and 16:

LeetCode 16

Python

class Solution:
    def threeSumClosest(self, nums, target):
        nums.sort()
        closest = nums[0] + nums[1] + nums[2]
        for i in range(len(nums) - 2):
            j = -~i
            k = len(nums) - 1
            while j < k:
                summation = nums[i] + nums[j] + nums[k]
                if summation == target:
                    return summation
                if abs(summation - target) < abs(closest - target):
                    closest = summation
                if summation < target:
                    j += 1
                elif summation > target:
                    k -= 1
        return closest

Java

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closest = nums[0] + nums[nums.length >> 1] + nums[nums.length - 1];

        for (int first = 0; first < nums.length - 2; first++) {
            int second = -~first;
            int third = nums.length - 1;

            while (second < third) {
                int sum = nums[first] + nums[second] + nums[third];

                if (sum > target)
                    third--;

                else
                    second++;

                if (Math.abs(sum - target) < Math.abs(closest - target))
                    closest = sum;
            }
        }

        return closest;
    }
}

LeetCode 15

Python

class Solution:
    def threeSum(self, nums):
        res = []
        nums.sort()
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            lo, hi = -~i, len(nums) - 1
            while lo < hi:
                tsum = nums[i] + nums[lo] + nums[hi]
                if tsum < 0:
                    lo += 1
                if tsum > 0:
                    hi -= 1
                if tsum == 0:
                    res.append((nums[i], nums[lo], nums[hi]))
                    while lo < hi and nums[lo] == nums[-~lo]:
                        lo += 1
                    while lo < hi and nums[hi] == nums[hi - 1]:
                        hi -= 1
                    lo += 1
                    hi -= 1
        return res

Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new LinkedList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
                int lo = -~i, hi = nums.length - 1, sum = 0 - nums[i];
                while (lo < hi) {
                    if (nums[lo] + nums[hi] == sum) {
                        res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                        while (lo < hi && nums[lo] == nums[-~lo])
                            lo++;
                        while (lo < hi && nums[hi] == nums[hi - 1])
                            hi--;
                        lo++;
                        hi--;
                    } else if (nums[lo] + nums[hi] < sum) {
                        lo++;
                    } else {
                        hi--;
                    }
                }
            }
        }
        return res;
    }
}

Reference

You can see the explanations in the following links:

LeetCode 15 - Discussion Board

LeetCode 16 - Discussion Board

LeetCode 15 - Solution

回答4:

You can use something like:

def find_3sum_restr(items, z):
    # : find possible items to consider -- O(n)
    candidates = []
    min_item = items[0]
    for i, item in enumerate(items):
        if item < z:
            candidates.append(i)
        if item < min_item:
            min_item = item
    # : find possible couples to consider -- O(n²)
    candidates2 = []
    for k, i in enumerate(candidates):
        for j in candidates[k:]:
            if items[i] + items[j] <= z - min_item:
                candidates2.append([i, j])
    # : find the matching items -- O(n³)
    for i, j in candidates2:
        for k in candidates:
            if items[i] + items[j] + items[k] == z:
                return i, j, k

This O(n + n² + n³), hence O(n³).

While this is reasonably fast for randomly distributed inputs (perhaps O(n²)?), unfortunately, in the worst case (e.g. for an array of all ones, with a z > 3), this is no better than the naive approach:

def find_3sum_naive(items, z):
    n = len(items)
    for i in range(n):
        for j in range(i, n):
            for k in range(j, n):
                if items[i] + items[j] + items[k] == z:
                    return i, j, k