CareerCup

This should be possible in O(n^2) time and space complexity.

First, you can rewrite the equation as x + y = w - z. Then create a nested loop where you calculate every possible value of x + y (ensuring the y-index always exceeds the x-index), and insert those values into a dictionary with the xy sum as the key. The dictionary value in this case would be an array containing the index of y. If you get xy sums that match existing keys, just add the new y index of those sums to the array returned by the dictionary.

Next, create an integer counter, and then create a second nested loop over the array, in which you'll compute every possible value of w - z (ensuring the w-index always exceeds the z-index). For each computed value, check the dictionary for a match. If you get one, loop over the returned array, and for each value that is less than your current z-index, increment the counter by 1.

It seems to me that time complexity of O(n^2) can be achieved by using hash map with keys as values of the array and values as indexes of the array (i.e. map[arr[i]] = i note that the array's elements are unique )
This map let us find z in O(1) by: z = W-arr[x]-arr[y], therefore we need to check: for each x and y in the array such that x<y if there is a z such that x+y+z = w.

code is Swift:

func comb(arr:[Int],W: Int) -> [(Int,Int,Int)]? {
    guard arr.count >= 3 else {
        return nil
    }
    var ia:[Int:Int] = [Int:Int]()
    var ret = [(Int,Int,Int)]()
    for i in 0..<arr.count {
        ia[arr[i]] = i
    }

    for x in 0..<arr.count-3 {
        for y in x+1..<arr.count-1 {
            let miss = W-arr[x]-arr[y]
            if let z = ia[miss] {
                if arr[x] + arr[y] + arr[z] == W && z > y {
                    ret.append((arr[x],arr[y],arr[z]))
                }
            }
        }
    }
    return ret
}

sorting might not help, there is a condition that idx(x)<idx(y).. as well.

public class SumArray1 {

    public int numOfSum(Integer[] arr) {
        if (null == arr || arr.length < 4) return -1;

        int count = 0;
        for (int x = 0; x < (arr.length - 3); x++) {
            for (int y = x+1; y < (arr.length - 2); y++) {
                for (int z = y+1; z < (arr.length - 1); z++) {
                    int tmpSum = arr[x] + arr[y] + arr[z];
                    // We can store the elements from w till end of the array into another array
                    // and then do the binary search in that array such that we get tmpSum
                    // This can reduce the complexity from O(n4) to O(n3 logn)
                    for (int w = z+1; w < arr.length; w++) {
                        if (tmpSum == arr[w]) {
                            count++;
                            break;
                        }
                    }
                }
            }
        }

        return count;
    }
}

public class SumArray1 {

    public int numOfSum(Integer[] arr) {
        if (null == arr || arr.length < 4) return -1;

        int count = 0;
        for (int x = 0; x < (arr.length - 3); x++) {
            for (int y = x+1; y < (arr.length - 2); y++) {
                for (int z = y+1; z < (arr.length - 1); z++) {
                    int tmpSum = arr[x] + arr[y] + arr[z];
                    // We can store the elements from w till end of the array into another array
                    // and then do the binary search in that array such that we get tmpSum
                    // This can reduce the complexity from O(n4) to O(n3 logn)
                    for (int w = z+1; w < arr.length; w++) {
                        if (tmpSum == arr[w]) {
                            count++;
                            break;
                        }
                    }
                }
            }
        }

        return count;
    }
}

public class SumArray1 {

    public int numOfSum(Integer[] arr) {
        if (null == arr || arr.length < 4) return -1;

        int count = 0;
        for (int x = 0; x < (arr.length - 3); x++) {
            for (int y = x+1; y < (arr.length - 2); y++) {
                for (int z = y+1; z < (arr.length - 1); z++) {
                    int tmpSum = arr[x] + arr[y] + arr[z];
                    // We can store the elements from w till end of the array into another array
                    // and then do the binary search in that array such that we get tmpSum
                    // This can reduce the complexity from O(n4) to O(n3 logn)
                    for (int w = z+1; w < arr.length; w++) {
                        if (tmpSum == arr[w]) {
                            count++;
                            break;
                        }
                    }
                }
            }
        }

        return count;
    }

}

Tried w/ Python....

def find(nums):
    temp=[]
    for i in range(len(nums)):
        current = nums[i]
        right = nums[i+1:]
        for c in helper(right):
            a = sorted([current] + c)
            for amount in nums:
                if a not in temp and sum(a) == amount and a[0] < a[1] < a[2] < amount:
                    temp.append(a)
    print(temp)
    return len(temp)

def helper(a):
    temp = []
    for i in range(len(a)-1):
        for j in range(i+1, len(a)):
             if not [a[i], a[j]] in temp:
                 temp.append([a[i], a[j]])
    return temp

""" all unique num, not sorted input, negative num included """ 
print("Solution-1: ",find([-1,0,1,2,3,-2,5]))
print("Solution-1: ",find([10,2,3,7,8,6,4,5,9,1]))

another one i tried...

def find2(x):
    temp = []
    for i in range(len(x)-2):
        for j in range(i+1, len(x)-1):
            for k in range(j+1, len(x)):
                a = sorted([x[i], x[j], x[k]])
                for w in x:
                    if a[0]<a[1]<a[2]<w and a[0]+a[1]+a[2]==w:
                        temp.append((a[0], a[1], a[2]))
    print(temp)
    return len(temp)

print("Solution-2: ",find2([10,2,3,7,8,6,4,5,9,1]))

We are matching a 4-place predicate so the bruteforce is O(n^4). If anything, this resembles a 4-sum problem, definetely not a 3-sum as some have claimed.

The important thing to note from the description is that 3 elements matching the value of the 4th element must lie to the left of the 4th element. This lends itself to this straightforward approach:

def count(arr):
    ans = 0
    sums = defaultdict(int)
    for i,x in enumerate(arr[3:], 3):
        c = arr[i-1]
        for j,a in enumerate(arr[:i-2]):
            for b in arr[j+1:i-1]:
                sums[a+b+c] += 1
        ans += sums[x]
    return ans

O(N^3) runtime.

O(n^3) time.

#include <unordered_set>
#include <vector>
#include <iostream>

using namespace std;

int64_t Count(const vector<int>& a)
{
    vector<unordered_set<int>> right;
    right.resize(a.size());
    for (int i = 2; i < a.size(); ++i)
    {
        for (int j = i + 1; j < a.size(); ++j)
        {
            right[i].insert(a[j]);
        }
    }

    int64_t count = 0;
    for (int i = 0; i < a.size(); ++i)
    {
        int sum1 = a[i];
        for (int j = i + 1; j < a.size(); ++j)
        {
            int sum2 = sum1 + a[j];
            for (int k = j + 1; k < a.size(); ++k)
            {
                int sum3 = sum2 + a[k];
                const unordered_set<int>& r = right[k];
                if (r.find(sum3) != r.end())
                {
                    ++count;
                }
            }
        }
    }

    return count;
}

int main()
{
    cout << Count({4, 1, 3, 8, 7, 12}) << "\n";
    return 0;
}

Brute force O(n^4), using a hash with a triple for loop O(n^3), but there is an O(n^2 log n) too.
Generate all sums x[j] - x[i] with i<j, takes O(n^2), put it in a hashmap with key as the sum, value a list where you append 'i'. This list is sorted, so finding how many values of 'i' are bigger than some index 'b' takes logN. Generate, all sums x[a]+x[b] with a<b, look up the sum in the hashmap, binary search to find how many of those sums are after index b.

We need to find solution in nlogn

3 sum problem [sorting nlogn + iteration n^2]
--> n^2 time complexity
--> O(1) Space Complexity