3Sum问题

作者: Azur_wxj | 来源:发表于2019-03-29 16:32 被阅读0次

3Sum Closest
LeetCode：15. 三数之和
3Sum问题
3Sum问题
Letter Combinations of a Phone N
Leetcode - Array [持续更新]
15. 3Sum
15. 三数之和
16. 3Sum Closest
数组

问题

给定一个整数数组 $A=[a_1,a_2,\cdots,a_n]$ ，找出数组中所有的三元组 $(a,b,c)$ ，满足 $a+b+c=0$ 三元组不允许重复，即对于 $(a_1,a_2,a_3)$ ，若 $p_1,p_2,p_3$ 是 $1,2,3$ 的一个排列数，那么 $(a_{p_1},a_{p_2},a_{p_3})$ 与 $(a_1,a_2,a_3)$ 是重复的。
例如， $(1,-5,4)$ 和 $(4,1,-5)$ 属于同一个三元组，但 $(0,0,0)$ 和 $(2,2,-4)$ 则是不同的三元组。可以把三元组认为是一个组合。

分析

一种解法是暴力解法，使用三重循环依次遍历数组，但这样时间复杂度会达到 $O(n^3)$ 。

先来考虑一个简单情况，即如果整数数组 $A$ 是一个有序数组，例如，非降序数组，即对于数组 $A=[a_1,a_2,\cdots,a_n]\quad(a_i\in{\mathbb Z})$ 有 $a_1\leqslant a_2 \leqslant \cdots \leqslant a_n$ 。那么可以从左往右按顺序寻找解。

例如，固定 $a_1$ ，我们将在 $a_2,a_3,\cdots,a_n$ 中寻找剩下的两个数 $a_\alpha,a_\beta$ ，使得 $a_1+a_\alpha+a_\beta=0$ 。按照这个顺序，对于 $a_i(i=1,2,\cdots,n-2)$ ，将在 $a_{i+1},a_{i+2},\cdots,a_n$ 中寻找 $a_\alpha,a_\beta$ ，使得 $(a_i,a_\alpha,a_\beta)$ 成为欲求的解，其解集设为 $R_i(i=1,2,\cdots,n-2)$ ，即 $R_i=\{(a_i,a_\alpha,a_\beta)| a_i+a_\alpha+a_\beta=0 ,\alpha\neq \beta, a_\alpha,a_\beta\in A[i+1:n]\}$
这里，符号 $A[i+1:n]$ 表示子数组 $[a_{i+1},\cdots,a_n]$ 。

定理1 对于非递减整数数列 $A$ 的两个元素 $a_i,a_{i+1}$ ，若 $a_i=a_{i+1}$ ，则 $R_i \supseteq R_{i+1}$ 。

证明

对于 $R_i$ ，将其内的每一个元素 $t=(a_i,a_\alpha,a_\beta)$ 按照断言 $P:=\left[ \left( \alpha\:{\bf is}\:(i+1) \right) {\bf or} \left( \beta\:{\bf is}\:(i+1) \right)\right]$ 进行分组。令 $R^+_i=\{t|P(t)=true,t\in R_i\}$ 以及 $R^-_i=\{t|P(t)=false,t\in R_i\}$ 显然 $R^+_i\cup R^-_i=R_i$ 且 $R^+_i\cap R^-_i=\varnothing$ 。

对于 $R^-_i$ ，因为其内元素的断言 $P$ 为假，因此 $\alpha\neq (i+1)$ 且 $\beta\neq(i+1)$ 。从而
$R^-_i=\{(a_{i},a_\alpha,a_\beta)| a_i+a_\alpha+a_\beta=0 ,\alpha\neq \beta, a_\alpha,a_\beta\in A[i+2:n]\}$
又因为 $a_i=a_{i+1}$ ，从而
$R^-_i=\{(a_{i+1},a_\alpha,a_\beta)| a_{i+1}+a_\alpha+a_\beta=0 ,\alpha\neq \beta, a_\alpha,a_\beta\in A[i+2:n]\}$
而这正是 $R_{i+1}$ 的定义，即 $R_{i+1}=R^-_i$ 。因此 $R_{i+1}\cup R^+_i=R_i$ 所以， $R_i\supseteq R_{i+1}$ ，证明完毕 ▇▇。

推论1 对于非递减整数数列 $A$ 的两个元素 $a_i,a_{j}$ ，若 $i<j$ 且 $a_i=a_{j}$ ，则 $R_i \supseteq R_{j}$ 。

证明
设 $a_{i+1},a_{i+2},\cdots,a_{j-1}$ 是介于 $a_i,a_{j}$ 中的元素，因为 $A$ 是非递减整数数列，且 $a_i=a_{j}$ ，这必然有 $a_i=a_{i+1}=a_{i+2}=\cdots=a_{j-1}=a_{j}$ 。反复使用定理1，就有 $R_i\supseteq R_{i+1}\supseteq R_{i+2}\supseteq \cdots \supseteq R_{j-1}\supseteq R_{j}$ 命题得证 ▇▇。

从推论1可知，如果我们找到了 $R_i$ ，如果接下来的元素值等于 $a_i$ ，那么可以跳过，直到遇到第一个 $a_j\neq a_i$ ，继续寻找 $R_j$ 。

下面这个定理说明，不同的数组元素的所生成的元组集合也不同。

定理2 对于非递减整数数列 $A$ 的两个元素 $a_i,a_{j}$ ，若 $a_i\neq a_{j}$ ，则 $R_i \cap R_{j}=\varnothing$ 。

不妨设 $a_i<a_{j}$ ，则 $R_j$ 中任意元组都含有 $a_j$ 而不含有 $a_i$ ，而 $R_i$ 中任意元组都含有 $a_i$ ，因此 $R_i \cap R_{j}=\varnothing$ ，证明完毕 ▇▇。

这个定理在用计算机求解该问题时很有用，因为我们不需要在找到一个解时去判断该解是否已经存在，直接加入结果集合即可。

现在我们需要一个算法能求出 $R_i$ 。

定理3 给定非递减整数数列 $A$ ，能够在有限步之内求出 $R_i$

证明

这是一个构造性证明，证明过程即是求出 $R_i$ 的算法。

考虑子列 $A[i:n]=[a_i,a_{i+1},\cdots,a_n]$ ，初始时， $R'_i=\varnothing$ 。
如果 $|A[i:n]|=(n-i+1)<3$ ，则不存在满足条件的三元组，证明结束。

否则，令 $\alpha=i+1\;,\beta=n$ ，显然 $\beta>\alpha$ 。设 $s=a_i+a_\alpha+a_\beta$ 。

如果 $s>0$ ，我们需要减小 $a_\beta$ ，可令 $\beta=\beta-1$ ；如果 $s<0$ ，我们需要增大 $a_\alpha$ ，可令 $\alpha=\alpha+1$ 。更新相关变量后再重新计算 $s$ ，可以使得 $s$ 不断向 $0$ 靠近。
假设当 $\alpha=\alpha_0\;,\beta=\beta_0$ 时， $s=0$ ，此时我们找到了一个解，则令 $R'_i=R'_i\cap\{(a_i,a_{\alpha_0},a_{\beta_0})\}$ ，以便将解添加到解集中。接下来，我们需要同步修改 $\alpha,\beta$ 的值。这是因为，假设我们令 $\alpha=\alpha_0$ 保持不变，而修改参数 $\beta$ ，则当且仅当 $\beta=\beta_0$ 时 $s=0$ ，但是这个解已经存在了。我们还必须注意到，如果 $a_{\alpha_0}=a_{\alpha_0+1}\;,a_{\beta_0}=a_{\beta_0-1}$ ，则得到的三元组 $(a_i,a_{\alpha_0+1},a_{\beta_0-1})$ 也是重复的。这启发我们可以使用如下的修改策略：找到最小正整数 $m$ ，使得 $a_{\alpha_0}=a_{\alpha_0+1}=\cdots=a_{\alpha_0+m-1}<a_{\alpha_0+m}$ 以及 $a_{\beta_0-m}<a_{\beta_0+m+1}=\cdots=a_{\beta_0-1}=a_{\beta_0}$ ,从而令 $\alpha=\alpha+m\;,\beta=\beta-m$ ，继续寻找下一组解。

由于初始时 $\beta>\alpha$ ，且在寻找解的过程中 $\alpha$ 不断增加， $\beta$ 不断减少，因此在有限步后必然会出现 $\alpha\geqslant\beta$ ，此时算法停止。我们还要证明，此时的 $R'_i$ 就是所求的解集 $R_i$ 。

显然 $R'_i\subseteq R_i$ 。假设 $R_i$ 中还有一组解 $(a_i,a_{\alpha'},a_{\beta'})\not\in R'_i$ ，不妨设 $\alpha'<\beta'$ 。在算法停止之前始终有 $\beta>\alpha$ ，且在算法停止时 $\beta\leqslant\alpha$ ，这就意味着在某一时刻有 $\alpha=\alpha'$ ，但此时 $\beta>\beta'$ 或者 $\beta<\beta'$ ，否则解就在 $R'_i$ 中。
如果 $\beta>\beta'$ ，那么 $s=a_i+a_{\alpha'}+a_{\beta}>a_i+a_{\alpha'}+a_{\beta'}=0$ ，根据算法，此时要使 $\beta=\beta-1$ ，如果此时 $s=a_i+a_{\alpha'}+a_{\beta}>0$ ，就不断使 $\beta=\beta-1$ ，这样一定可以使得 $\beta=\beta'$ ，因此解 $(a_i,a_{\alpha'},a_{\beta'})\in R'_i$ 。
另一方面，如果 $\beta<\beta'$ ，说明在之前某个时刻曾有 $\beta=\beta'\;,\alpha<\alpha'$ （因为当前时刻 $\alpha=\alpha'$ ，而 $\alpha$ 不可能减少，所以此前时刻 $\alpha\leqslant\alpha'$ ，但如果等号成立则与条件矛盾，因此只取小于号。），于是 $s=a_i+a_{\alpha}+a_{\beta'}<a_i+a_{\alpha'}+a_{\beta'}=0$ ，根据算法就要让 $\alpha=\alpha+1$ ，不断重复就一定可以使得 $\alpha=\alpha'$ ，因此解 $(a_i,a_{\alpha'},a_{\beta'})\in R'_i$ 。

因为无论 $\beta>\beta'$ 或者 $\beta<\beta'$ 都会产生矛盾，所以 $R_i$ 中不存在解 $(a_i,a_{\alpha'},a_{\beta'})\not\in R'_i$ ，所以 $R'_i=R_i$ 即为所求，证明完毕 ▇▇。

下面这个定理给出非降序序列问题的解

定理4 若给定一个非降序整数数组 $A=[a_1,a_2,\cdots,a_n]\;(a_i\leqslant a_j,{\rm if}\;i<j)$ ，满足 $a+b+c=0$ 的所有不重复三元组 $(a,b,c)$ 的集合 $R(A)$ 为 $R(A)=\cup_{i={\bf unidx}(A)}R_i$ 其中 ${\bf unidx}(A)$ 给出 $A$ 中不重复元素的下标序列 $[i_1,i_2,\cdots,i_k]$ ，使得对于 $i_p< i_q$ ，有 $a_{i_p}=a_{i_p+1}=\cdots=a_{i_q-1}<a_{i_q}$ 。特别的， $a_{i_1}=a_1\;,a_{i_k}=a_{i_k+1}=\cdots=a_n$ 。例如，对于 $A=[-5,-4,-4,0,0,2,3,1,1,1]$ ， ${\bf unidx}(A)=[1,2,4,6,7,8]$ 。

该定理使用推论1和定理2、定理3容易证明 ▇▇。

代码

使用JavaScript代码进行实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const LENGTH=nums.length;
    if(LENGTH<3) return [];
    nums.sort((a,b)=>a-b); 
    let result = [],ai=nums[0],j=1,k=LENGTH-1,jksum=0,lastAi=undefined,lastAj=undefined,lastAk=undefined;
    for (let i = 0; i < LENGTH - 2; lastAj=lastAk=undefined,++i,j=i+1,k=LENGTH-1,ai=nums[i]) {
        if(lastAi===ai) continue;
        while(j<k){
            if(lastAj===nums[j]&&lastAk===nums[k]){j++,k--;continue;}
            if((jksum=nums[j]+nums[k])===-ai){
                lastAj=nums[j],lastAk=nums[k],lastAi=ai;
                result.push([ai,nums[j],nums[k]]);
                j++,k--;
            }else{ jksum>-ai/*ai+aj+ak>0*/?k--:j++;}
        } 
    }
    return result;
};

//test cases


[
    [-5, -5, -4, -4, -4, -2, -2, -2, 0, 0, 0, 1, 1, 3, 4, 4]
].forEach((v,i)=>{
    console.log(`for the ${i}th case ${showArrayDeeply(v)}, your output is ${showArrayDeeply(threeSum(v))}`);
});

//helper method
function showArrayDeeply(arr){
    var result=[];
    (function show(arr,jar){
        let subjar=[]
        for(let ele of arr){
            if(Array.isArray(ele)) show(ele,subjar);
            else subjar.push(ele+"");
        }
        if(subjar.length>0) jar.push('['+subjar.join(',')+']');
    })(arr,result);
    return '['+result.join(',')+']';
};

3Sum Closest
每日算法——leetcode系列问题 3Sum Closest Difficulty: Medium Given...
LeetCode：15. 三数之和
问题链接 15. 三数之和[https://leetcode-cn.com/problems/3sum/] 问题描...
3Sum问题
Given an array S of n integers, are there elements a, b, ...
3Sum问题
问题给定一个整数数组，找出数组中所有的三元组，满足三元组不允许重复，即对于，若是的一个排列数，那么与是重复的。...
Letter Combinations of a Phone N
标签： C++ 算法 LeetCode 字符串每日算法——leetcode系列问题 3Sum Closest ...
Leetcode - Array [持续更新]
15. 3Sum --- Medium[https://leetcode.com/problems/3sum/]1...
15. 3Sum
15. 3Sum 题目:https://leetcode.com/problems/3sum/ 难度: Mediu...
15. 三数之和
题目地址(3sum/">15. 三数之和) https://leetcode.cn/problems/3sum/[...
16. 3Sum Closest
与3Sum思路相同
数组
数组题目总结 sum类型的题 leetcode 2sum leetcode 15. 3Sum思路：将3sum转化成...