LeetCode 923 - 3Sum With Multiplicity

https://leetcode.com/problems/3sum-with-multiplicity/

Given an integer array A, and an integer target, return the number of tuples i, j, k  such that i < j < k and A[i] + A[j] + A[k] == target.

As the answer can be very large, return it modulo 10^9 + 7.

Example 1:

Input: A = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation: 
Enumerating by the values (A[i], A[j], A[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.

Example 2:

Input: A = [1,1,2,2,2,2], target = 5
Output: 12
Explanation: 
A[i] = 1, A[j] = A[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.

Note:

1. 3 <= A.length <= 3000
2. 0 <= A[i] <= 100
3. 0 <= target <= 300

X. Map store pair sum
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181128/10-lines-Super-Super-Easy-Java-Solution

    public int threeSumMulti(int[] A, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        
        int res = 0;
        int mod = 1000000007;
        for (int i = 0; i < A.length; i++) {
            res = (res + map.getOrDefault(target - A[i], 0)) % mod;
            
            for (int j = 0; j < i; j++) {
                int temp = A[i] + A[j];
                map.put(temp, map.getOrDefault(temp, 0) + 1);
            }
        }
        return res;
    }




public int threeSumMulti(int[] A, int target) {
        HashMap<Integer, Integer> count = new HashMap<>();
        int n = A.length;
        long result = 0;
        
        for(int i = 0; i + 1 < n; i++){
            for(int j = i + 1; j < n; j++){
                if(count.containsKey(target - A[i] - A[j])){
                    result += 1L * count.get(target - A[i] - A[j]); 
                    //System.out.println(result);
                }
            }
            count.put(A[i], count.getOrDefault(A[i], 0) + 1);
        }
        
       // System.out.println(result);
        return (int) (result%(1000000000 + 7));
    }

https://leetcode.com/problems/3sum-with-multiplicity/discuss/181125/Knapsack-O(n-*-target)-or-Straightforward-O(n2)

    public int threeSumMulti(int[] A, int target) {
        Map<Integer, Long> map = new HashMap<>();
        for (int a : A) {
            map.put(a, map.getOrDefault(a, 0l) + 1);
        }
        long result = 0;
        int M = (int)1e9 + 7;
        for (int a : map.keySet()) {
            for (int b : map.keySet()) {
                if (b < a || a == b && map.get(a) == 1) {
                    continue;
                }
                int c = target - a - b;
                if (c < b || !map.containsKey(c)) {
                    continue;
                }
                if (a == b && b == c) {
                    if (map.get(a) == 2) {
                        continue;
                    }
                    result += nCk(map.get(a), 3);
                } else if (a == b) {
                    result += nCk(map.get(a), 2) * map.get(c);
                } else if (b == c) {
                    if (map.get(b) == 1) {
                        continue;
                    }
                    result += nCk(map.get(b), 2) * map.get(a);
                } else {
                    result += (map.get(a) * map.get(b) * map.get(c));
                }
                result %= M;
            }
        }
        return (int)result;
    }
    private long nCk(long n, int k) {
        if (k == 3) {
            return (n * (n - 1) * (n - 2)) / 6;
        } else {
            return n * (n - 1) / 2;
        }
    }




https://leetcode.com/problems/3sum-with-multiplicity/discuss/181131/C%2B%2BJavaPython-O(N-%2B-101-*-101)

Count the occurrence of each number.
using hashmap or array up to you.

Loop i on all numbers,
loop j on all numbers,
check if k = target - i - j is valid.

Add the number of this combination to result.
3 cases covers all possible combination:

1. i == j == k
2. i == j != k
3. i < k && j < k

Time Complexity:
3 <= A.length <= 3000, so N = 3000
But 0 <= A[i] <= 100
So my solution is O(N + 101 * 101)

    public int threeSumMulti(int[] A, int target) {
        long[] c = new long[101];
        for (int a : A) c[a]++;
        long res = 0;
        for (int i = 0; i <= 100; i++)
            for (int j = i; j <= 100; j++) {
                int k = target - i - j;
                if (k > 100 || k < 0) continue;
                if (i == j && j == k)
                    res += c[i] * (c[i] - 1) * (c[i] - 2) / 6;
                else if (i == j && j != k)
                    res += c[i] * (c[i] - 1) / 2 * c[k];
                else if (j < k)
                    res += c[i] * c[j] * c[k];
            }
        return (int)(res % (1e9 + 7));
    }

X. 3 pointers
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181098/Java-O(n2)-code-Sort-and-Match.

while (j + l < k && A[j + l] == A[j]) { ++l; } 
while (j < k - r && A[k - r] == A[k]) { ++r; }

solving the duplicated cases is quite impressive, that is the solution I am looking for

    private static final int  m = 1_000_000_007;
    public int threeSumMulti(int[] A, int target) {
        Arrays.sort(A);
        int res = 0;
        for (int i = 0; i < A.length - 2; ++i) {
            int j = i + 1;
            int k = A.length - 1;
            while (j < k) {
                if (A[j] + A[k] < target - A[i]) { ++j; }
                else if (A[j] + A[k] > target - A[i]) { --k; }
                else {
                    if (A[j] == A[k]) {
                        // If A[j...k] are all equal, then there are C(k - j + 1, 2) 
                        // combinations that meet the requirement.
                        res = (res + (k - j + 1) * (k - j) / 2) % m;
                        break;
                    }
                    int l = 1, r = 1;
                    while (j + l < k && A[j + l] == A[j]) { ++l; } // l: number of elements equal to A[j].
                    while (j < k - r && A[k - r] == A[k]) { ++r; } // r: number of elements equal to A[k].
                    res = (res + l * r) % m; // found l * r cases that meet the requirement.
                    j += l; // forward j by l steps.
                    k -= r; // backward k by r steps.
                }
            }
        }
        return res;
    }

X. DP
https://leetcode.com/problems/3sum-with-multiplicity/discuss/181125/Knapsack-O(n-*-target)-or-Straightforward-O(n2)

dp[i][j][k] represents number of combinations using k numbers within A[0] ... A[i] with the sum of j.
Then dp[n][target][3] is the result. O(n * target)

    public int threeSumMulti(int[] A, int target) {
        int n = A.length, M = (int)1e9 + 7;
        int[][][] dp = new int[n + 1][target + 1][4];
        for (int i = 0; i <= n; i++) {
            dp[i][0][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= target; j++) {
                for (int k = 1; k <= 3; k++) {
                    dp[i + 1][j][k] = dp[i][j][k];
                    dp[i + 1][j][k] %= M;
                    if (j >= A[i]) {
                        dp[i + 1][j][k] += dp[i][j - A[i]][k - 1];
                        dp[i + 1][j][k] %= M;
                    }
                }
            }
        }
        return dp[n][target][3];
    }




X. https://zxi.mytechroad.com/blog/math/leetcode-923-3sum-with-multiplicity/

Time complexity: O(n + |target|^2)

Space complexity: O(|target|)

https://my.oschina.net/yysue/blog/2250875

# step1 统计数组中每个元素出现的次数
一个元素I出现的次数记为count(I)

# step2 分类
记：I=A[i], J=A[j], K=A[k], C(count(I),3) 表示从count(I)个数中取3个的组合数
I=J=K     C(count(I), 3)
I=J!=K    C(count(I), 2) * count(K)
I!=J=K    count(I) * C(count(K), 2)
I!=J!=K   count(I) * count(J) * count(K)

# 复杂度
Time complexity: O(n + target^2)
Space complexity: O(100)

下面是参考视频中的截图，其中的i,j,k是数而不是index

public int threeSumMulti(int[] A, int target) {
    int MOD = 1_000_000_007; // 因为最大数为10^9+7

    // 计算数组中不同元素出现的个数   因为 0 <= A[i] <=100
    long[] c = new long[101]; // 定义成long，在计算中不用转换
    for (int a : A) c[a]++;

    long ans = 0;
    for (int i = 0; i <= target; i++) {
        for (int j = i; j <= target; j++) {
            int k = target - i - j;
            if (k < 0 || k >= c.length || k < j) continue;
            if (c[i] == 0 || c[j] == 0 || c[k] == 0) continue;
            if (i ==j && j == k) {
                ans += (c[i] - 2) * (c[i] - 1) * c[i] / 6;
            } else if (i ==j && j != k) {
                ans += c[i] * (c[i] - 1) / 2 * c[k];
            } else if (i != j && j == k) {
                ans += c[i] * (c[j] - 1) * c[j] / 2;
            } else {
                ans += c[i] * c[j] * c[k];
            }
            ans %= MOD;
        }
    }
    return (int)ans;
}

  public int threeSumMulti(int[] A, int target) {

    int MOD = 1_000_000_007;

    long ans = 0;

    Arrays.sort(A);

    for (int i = 0; i < A.length; ++i) {

      // We'll try to find the number of i < j < k

      // with A[j] + A[k] == T, where T = target - A[i].

      // The below is a "two sum with multiplicity".

      int T = target - A[i];

      int j = i + 1, k = A.length - 1;

      while (j < k) {

        // These steps proceed as in a typical two-sum.

        if (A[j] + A[k] < T)

          j++;

        else if (A[j] + A[k] > T)

          k--;

        else if (A[j] != A[k]) { // We have A[j] + A[k] == T.

          // Let's count "left": the number of A[j] == A[j+1] == A[j+2] == ...

          // And similarly for "right".

          int left = 1, right = 1;

          while (j + 1 < k && A[j] == A[j + 1]) {

            left++;

            j++;

          }

          while (k - 1 > j && A[k] == A[k - 1]) {

            right++;

            k--;

          }

          ans += left * right;

          ans %= MOD;

          j++;

          k--;

        } else {

          // M = k - j + 1

          // We contributed M * (M-1) / 2 pairs.

          ans += (k - j + 1) * (k - j) / 2;

          ans %= MOD;

          break;

        }

      }

    }

    return (int) ans;

  }

  public int threeSumMulti(int[] A, int target) {

    int MOD = 1_000_000_007;

    long[] count = new long[101];

    for (int x : A)

      count[x]++;

    long ans = 0;

    // All different

    for (int x = 0; x <= 100; ++x)

      for (int y = x + 1; y <= 100; ++y) {

        int z = target - x - y;

        if (y < z && z <= 100) {

          ans += count[x] * count[y] * count[z];

          ans %= MOD;

        }

      }

    // x == y != z

    for (int x = 0; x <= 100; ++x) {

      int z = target - 2 * x;

      if (x < z && z <= 100) {

        ans += count[x] * (count[x] - 1) / 2 * count[z];

        ans %= MOD;

      }

    }

    // x != y == z

    for (int x = 0; x <= 100; ++x) {

      if (target % 2 == x % 2) {

        int y = (target - x) / 2;

        if (x < y && y <= 100) {

          ans += count[x] * count[y] * (count[y] - 1) / 2;

          ans %= MOD;

        }

      }

    }

    // x == y == z

    if (target % 3 == 0) {

      int x = target / 3;

      if (0 <= x && x <= 100) {

        ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6;

        ans %= MOD;

      }

    }

    return (int) ans;

  }

  public int threeSumMulti(int[] A, int target) {

    int MOD = 1_000_000_007;

    // Initializing as long saves us the trouble of

    // managing count[x] * count[y] * count[z] overflowing later.

    long[] count = new long[101];

    int uniq = 0;

    for (int x : A) {

      count[x]++;

      if (count[x] == 1)

        uniq++;

    }

    int[] keys = new int[uniq];

    int t = 0;

    for (int i = 0; i <= 100; ++i)

      if (count[i] > 0)

        keys[t++] = i;

    long ans = 0;

    // Now, let's do a 3sum on "keys", for i <= j <= k.

    // We will use count to add the correct contribution to ans.

    for (int i = 0; i < keys.length; ++i) {

      int x = keys[i];

      int T = target - x;

      int j = i, k = keys.length - 1;

      while (j <= k) {

        int y = keys[j], z = keys[k];

        if (y + z < T) {

          j++;

        } else if (y + z > T) {

          k--;

        } else { // # x+y+z == T, now calc the size of the contribution

          if (i < j && j < k) {

            ans += count[x] * count[y] * count[z];

          } else if (i == j && j < k) {

            ans += count[x] * (count[x] - 1) / 2 * count[z];

          } else if (i < j && j == k) {

            ans += count[x] * count[y] * (count[y] - 1) / 2;

          } else { // i == j == k

            ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6;

          }

          ans %= MOD;

          j++;

          k--;

        }

      }

    }

    return (int) ans;

  }

Lintcode: K Sum I

Related: Lintcode K Sum II
http://www.cnblogs.com/yuzhangcmu/p/4279676.html
http://www.jiuzhang.com/solutions/k-sum/
https://github.com/yuzhangcmu/LeetCode/blob/master/lintcode/dp/KSum.java
Given n distinct positive integers, integer k (k <= n) and a number target. Find k numbers where sum is target.
Calculate how many solutions there are?

    public int  kSum1(int A[], int k, int target) {
 9         if (target < 0) {
10             return 0;
11         }
12         
13         int len = A.length;
15         int[][][] D = new int[len + 1][k + 1][target + 1];
16         
17         for (int i = 0; i <= len; i++) {
18             for (int j = 0; j <= k; j++) {
19                 for (int t = 0; t <= target; t++) {
20                     if (j == 0 && t == 0) {
21                         // select 0 number from i to the target: 0
22                         D[i][j][t] = 1;
23                     } else if (!(i == 0 || j == 0 || t == 0)) {
24                         D[i][j][t] = D[i - 1][j][t];
25                         if (t - A[i - 1] >= 0) {
26                             D[i][j][t] += D[i - 1][j - 1][t - A[i - 1]];
27                         }
28                     }
29                 }
30             }
31         }
32         
33         return D[len][k][target];
34     }

我们可以把最外层的Matrix可以省去。

这里最优美的地方，在于我们把target作为外层循环，并且从右往左计算。这里的原因是：

D[i][j][t] += D[i - 1][j - 1][t - A[i - 1]];

这个表达式说明D[i][j][t]是把上一级i的结果累加过来。这里我们省去了i这一级，也就是说在D[j][t]这个表里就地累加。而且t - A[i - 1]小于t。

在以下图表示就是说D[j][t]是来自于上一行的在t左边的这些值中挑一些加起来。

所以我们就必须从右往左逐列计算来避免重复的累加。

1. 如果你从左往右按列计算，每一列会被重复地加总，就会有重复计算。我们可以想象一下，len = 0为上表，len = 1为下表。

现在我们只有一个表，就是下面这个（因为第一个维度被取消了），现在如果你从左往右计算，被sum的区域会被填掉，覆盖

len = 0 那张表留下的值，下一个值的计算就不会准确了。

2. 或者如果你逐行计算，也是不可以的。因为你也是把生成D[j][t](在图里写的是D[i][j])的被sum的区域覆盖，也会造成结果不准确。

3. 所以，只要我们逐列计算，并且顺序是从右往左，即使我们只有一个二维表，我们的被sum区域也可以保持洁净，从空间角度来想，

就相当于从len=0那张表中取值。

总结：这种思维方式可能在面试里很难遇到，不过，可以开拓我们思维，这里同样是动规时如果取得上一级的值的问题，并且它考虑了省

去一级，就地利用二维空间的值，那么就要考虑我们上一级的旧表不要被覆盖。可以在大脑中构思一个三维空间，一个三维表由多个二维

表构成，如果把它们用一个表来做，再思考一下即可。

 1 // 2 dimension
 2     public int  kSum(int A[], int k, int target) {
 4         if (target < 0) {
 5             return 0;
 6         }
 7         
 8         int len = A.length;
 9         
10         // D[i][j]: k = i, target j, the solution.
11         int[][] D = new int[k + 1][target + 1];
12         
13         // only one solution for the empty set.
14         D[0][0] = 1;
15         for (int i = 1; i <= len; i++) {
16             for (int t = target; t > 0; t--) {
17                 for (int j = 1; j <= k; j++) {
18                     if (t - A[i - 1] >= 0) {
19                         D[j][t] += D[j - 1][t - A[i - 1]];
20                     }
21                 }
22             }
23         }
24         
25         return D[k][target];
26     }

https://www.jiuzhang.com/solution/k-sum/


https://github.com/yuzhangcmu/LeetCode/blob/master/lintcode/dp/KSum.java
public int  kSum(int A[], int k, int target) {
    // write your code here
    if (target < 0) {
        return 0;
    }
 
    int len = A.length;
 
    // D[i][j]: k = i, target j, the solution.
    int[][] D = new int[k + 1][target + 1];
 
    // only one solution for the empty set.
    D[0][0] = 1;
    for (int i = 1; i <= len; i++) {
     
            for (int j = 1; j <= k; j++) {
                for (int t = target; t > 0; t--) {
                if (t - A[i - 1] >= 0) {
                    D[j][t] += D[j - 1][t - A[i - 1]];
                }
            }
        }
    }
 
    return D[k][target];
}

X. DFS
http://blog.csdn.net/wankunde/article/details/44058097
思路一： 迭代，开始时依次选择一个点，然后根据新的target值和新的数组，选择k-1个数，思路直接简单。但是存在重复计算。该算法复杂度为 Nk ,指数递增，所以在lintcode中就计算超时了。
public int kSum(int A[], int k, int target) { if (A.length < k || k == 0) return 0; if(k == 1){ for(int i=0;i<A.length;i++) if(A[i] == target) return 1; return 0; } else { int[] B = new int[A.length - 1]; if (A.length > 1) System.arraycopy(A, 1, B, 0, A.length - 1); return kSum(B, k - 1, target - A[0]) + kSum(B, k, target); } }
http://blog.welkinlan.com/2015/08/20/k-sum-i-ii-lintcode-java/
We can use backtracking to solve this problem, which is O(n^k). However, this is TLE    public int kSum(int A[], int k, int target) {

        // write your code here

        ArrayList<Integer> result = new  ArrayList<Integer>();

        if (A == null || A.length == 0) {

            return 0;

        }

        result.add(0);

        helper(A, k, target, result, 0, new ArrayList<Integer>());

        return result.get(0);

    }

    

    private void helper(int A[], int k, int target, ArrayList<Integer> result, int curIndex, ArrayList<Integer> curList) {

        if (curList.size() == k) {

            if (target == 0) {

                result.set(0, result.get(0) + 1);

            }

            return;

        }

        for (int i = curIndex; i < A.length; i++) {

            curList.add(A[i]);

            helper(A, k, target - A[i], result, i + 1, curList);

            curList.remove(curList.size() - 1);

        }

    }

http://codeanytime.blogspot.com/2014/12/lintcode-k-sum.html

    void helper(vector<int> A,int k, int start,int target, int & ans) {
        if (k < 0 || target < 0) return;
        if (k == 0 && target == 0) {
            ans++;
            return;
        }
        for(int i = start; i <= A.size()-k; i++)
            helper(A, k-1, i+1, target - A[i], ans);
    }
    int solutionKSum(vector<int> A,int k,int target) {
        int ans = 0;
        helper(A, k, 0, target, ans);
        return ans;
    }

//打印所有方案版本

  int[] res;

  int tot;

  int[] A;

  int K;

  int[][][] f;

  void printAnswer(int i, int j, int k) {

    if (j == 0) {

      for (int h = 0; h < K; ++h) {

        System.out.print(res[h]);

        if (h == K - 1) {

          System.out.println("=" + tot);

        } else {

          System.out.print("+");

        }

      }

      return;

    }

    if (f[i - 1][j][k] > 0) {

      printAnswer(i - 1, j, k);

    }

    if (j > 0 && k >= A[i - 1] && f[i - 1][j - 1][k - A[i - 1]] > 0) {

      res[j - 1] = A[i - 1];

      printAnswer(i - 1, j - 1, k - A[i - 1]);

    }

  }

  public int kSum(int[] AA, int KK, int T) {

    K = KK;

    A = AA;

    int n = A.length;

    res = new int[K];

    tot = T;

    f = new int[n + 1][K + 1][T + 1];

    int i, j, k;

    for (j = 0; j <= K; ++j) {

      for (k = 0; k <= T; ++k) {

        f[0][j][k] = 0;

      }

    }

    f[0][0][0] = 1;

    for (i = 1; i <= n; ++i) {

      for (j = 0; j <= K; ++j) {

        for (k = 0; k <= T; ++k) {

          // not using A[i - 1]

          f[i][j][k] = f[i - 1][j][k];

          // using A[i - 1]

          if (j > 0 && k >= A[i - 1]) {

            f[i][j][k] += f[i - 1][j - 1][k - A[i - 1]];

          }

        }

      }

    }

    printAnswer(n, K, T);

    return f[n][K][T];

  }

另外，还有一些题目的变形，比如如果要求所有组合，满足
sum < k,
sum = k,
sum > k,
或者是 closest to k