09、JS实现：数组三数之和算法的解决方案(一步一步剖析，很详细)

ⅰ、数组三数之和的算法：

1、题目描述：

2、解题思路：

3、实现代码：

其一、代码为：

// 数组三数之和算法的函数：
const threesum = (nums, target) => {
  let res = []
  let sum = target
  // 将数组元素排序
  nums.sort((a, b) => {
    return a - b
  })

  const len = nums.length
  for (let i = 0; i < len - 2; i++) {
    let j = i + 1
    let k = len - 1

    // 如果有重复数字就跳过
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue
    }

    while (j < k) {
      // 三数之和⼩于 sum 值，左指针右移
      // if (nums[i] + nums[j] + nums[k] < 0) {
      if (nums[i] + nums[j] + nums[k] < sum) {
        j++
        // 处理左指针元素重复的情况
        while (j < k && nums[j] === nums[j - 1]) {
          j++
        }
        // 三数之和⼤于0，右指针左移
        // } else if (nums[i] + nums[j] + nums[k] > 0) {
      } else if (nums[i] + nums[j] + nums[k] > sum) {
        k--
        // 处理右指针元素重复的情况
        while (j < k && nums[k] === nums[k + 1]) {
          k--
        }
      } else {
        // 储存符合条件的结果
        res.push([nums[i], nums[j], nums[k]])
        j++
        k--
        while (j < k && nums[j] === nums[j - 1]) {
          j++
        }
        while (j < k && nums[k] === nums[k + 1]) {
          k--
        }
      }
    }
  }
  return res
}

// 此时的输出结果为：[ [ 1, 4, 10 ], [ 1, 5, 9 ], [ 1, 6, 8 ], [ 2, 3, 10 ], [ 2, 4, 9 ], [ 2, 5, 8 ], [ 2, 6, 7 ], [ 3, 4, 8 ], [ 3, 5, 7 ], [ 4, 5, 6 ] ];
threesum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 15)

    执行  threesum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 15)  函数后代码执行的过程：
    注意：其会先将 nums 数组进行升序排列为：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，target 为: 15;
    

    第一个循环：for (let i = 0; i < len - 2; i++) {}, len = 10, i=0，j=i+1=1, k=len-1=9, sum = 15 的情况：
	    且在 i=0 的情况下，类似 if (i > 0 && nums[i] === nums[i - 1]) {} 的所有判断都是不成立的;
	   		 j          k         nums[i] + nums[j] + nums[k] 与 sum 关系            j++        k--     
			 1    <     9         nums[0]+nums[1]+nums[9] = 1+2+10 < 15               2
			 2    <     9         nums[0]+nums[2]+nums[9] = 1+3+10 < 14               3
			 3    <     9         nums[0]+nums[3]+nums[9] = 1+4+10 = 15               
			 
			 res.push([1,4,10])，res为[[1,4,10]];                                     4         8
			 
			 4    <     8         nums[0]+nums[4]+nums[8] = 1+5+9 = 15      
			 
			 res.push([1,5,9])，res为[[1,4,10],[1,5,9]];                              5         7 
			 
			 5    <     7         nums[0]+nums[5]+nums[7] = 1+6+8 = 15                
			 
			 res.push([1,6,8])，res为[[1,4,10],[1,5,9],[1,6,8]];                      6         6 
			 
			 6    <     6     while (j < k) {} 不成立，循环结束;



    第一个循环：for (let i = 0; i < len - 2; i++) {}, len = 10, i=1，j=i+1=2, k=len-1=9, sum = 15 的情况：
	    且在 i=1 的情况下，类似 if (i > 0 && nums[i] === nums[i - 1]) {} 的所有判断都是不成立的;
	   		 j          k         nums[i] + nums[j] + nums[k] 与 sum 关系                             j++        k--    
	   		 2    <     9         nums[1]+nums[2]+nums[9] = 2+3+10 = 15              
	   		 
	   		 res.push([2,3,10])，res为[[1,4,10],[1,5,9],[1,6,8],[2,3,10]];                            3          8 
	   		 
	   		 3    <     8         nums[1]+nums[3]+nums[8] = 2+4+9 = 15              
	   		 
	   		 res.push([2,4,9])，res为[[1,4,10],[1,5,9],[1,6,8],[2,3,10],[2,4,9]];                     4          7 
	   		 
			 4    <     7         nums[1]+nums[4]+nums[7] = 2+5+8 = 15       
			 
			 res.push([2,5,8])，res为[[1,4,10],[1,5,9],[1,6,8],[2,3,10],[2,4,9],[2,5,8]];             5          6 
			 
			 5    <     6         nums[1]+nums[5]+nums[6] = 2+6+7 = 15        
			 
			 res.push([2,6,7])，res为[[1,4,10],[1,5,9],[1,6,8],[2,3,10],[2,4,9],[2,5,8],[2,6,7]];     6          5 
			     
			 6    <     5     while (j < k) {} 不成立，循环结束;  



    第一个循环：for (let i = 0; i < len - 2; i++) {}, len = 10, i=2，j=i+1=3, k=len-1=9, sum = 15 的情况：
	    且在 i=2 的情况下，类似 if (i > 0 && nums[i] === nums[i - 1]) {} 的所有判断都是不成立的;
	   		 j          k         nums[i] + nums[j] + nums[k] 与 sum 关系                                          j++        k--    
	   		 3    <     9         nums[2]+nums[3]+nums[9] = 3+4+10 > 15              						           	      8
	   		 3    <     8         nums[2]+nums[3]+nums[8] = 3+4+9 > 15              							              7
	   		 3    <     7         nums[2]+nums[3]+nums[7] = 3+4+8 = 15      
	   		         							
	   		 res.push([3,4,8])，res为[[1,4,10],[1,5,9],[1,6,8],[2,3,10],[2,4,9],[2,5,8],[2,6,7],[3,4,8]];          4          6  
	   		 
	   		 4    <     6         nums[2]+nums[4]+nums[6] = 3+5+7 = 15
	   		 
	   		 res.push([3,5,7])，res为[[1,4,10],[1,5,9],[1,6,8],[2,3,10],[2,4,9],[2,5,8],[2,6,7],[3,4,8],[3,5,7]];  5          5  
	   		 
	   		 5    <     5     while (j < k) {} 不成立，循环结束;  



    第一个循环：for (let i = 0; i < len - 2; i++) {}, len = 10, i=3，j=i+1=4, k=len-1=9, sum = 15 的情况：
	    且在 i=3 的情况下，类似 if (i > 0 && nums[i] === nums[i - 1]) {} 的所有判断都是不成立的;
	   		 j          k         nums[i] + nums[j] + nums[k] 与 sum 关系                                                  j++        k--    
	   		 4    <     9         nums[3]+nums[4]+nums[9] = 4+5+10 > 15                                                               8
	   		 4    <     8         nums[3]+nums[4]+nums[8] = 4+5+9 > 15                                                                7
	   		 4    <     7         nums[3]+nums[4]+nums[7] = 4+5+8 > 15                                                                6
	   		 4    <     6         nums[3]+nums[4]+nums[6] = 4+5+7 > 15                                                                5
	   		 4    <     5         nums[3]+nums[4]+nums[5] = 4+5+6 = 15    
	   		                                                             
	   		 res.push([4,5,6])，res为[[1,4,10],[1,5,9],[1,6,8],[2,3,10],[2,4,9],[2,5,8],[2,6,7],[3,4,8],[3,5,7],[4,5,6]];  5          4       
	   		 
	   		 5    <     4     while (j < k) {} 不成立，循环结束;  



    第一个循环：for (let i = 0; i < len - 2; i++) {}, len = 10, i=4，j=i+1=5, k=len-1=9, sum = 15 的情况：
	    且在 i=4 的情况下，类似 if (i > 0 && nums[i] === nums[i - 1]) {} 的所有判断都是不成立的;
	   		 j          k         nums[i] + nums[j] + nums[k] 与 sum 关系            j++        k--  
			 5    <     9         nums[4]+nums[5]+nums[9] = 5+6+10 > 15                         8   
			 5    <     8         nums[4]+nums[5]+nums[8] = 5+6+9 > 15                          7
			 5    <     7         nums[4]+nums[5]+nums[7] = 5+6+8 > 15                          6
			 5    <     6         nums[4]+nums[5]+nums[6] = 5+6+7 > 15                          5
			 5    <     5     while (j < k) {} 不成立，循环结束;  



	第一个循环：for (let i = 0; i < len - 2; i++) {}, len = 10, i=5，j=i+1=6, k=len-1=9, sum = 15 的情况：
	    且在 i=5 的情况下，类似 if (i > 0 && nums[i] === nums[i - 1]) {} 的所有判断都是不成立的;
	   		 j          k         nums[i] + nums[j] + nums[k] 与 sum 关系            j++        k--  
			 6    <     9         nums[5]+nums[6]+nums[9] = 6+7+10 > 15                         8   
			 6    <     8         nums[5]+nums[6]+nums[8] = 6+7+9 > 15                          7
			 6    <     7         nums[5]+nums[6]+nums[7] = 6+7+8 > 15                          6
			 6    <     6     while (j < k) {} 不成立，循环结束;  



	第一个循环：for (let i = 0; i < len - 2; i++) {}, len = 10, i=6，j=i+1=7, k=len-1=9, sum = 15 的情况：
	    且在 i=6 的情况下，类似 if (i > 0 && nums[i] === nums[i - 1]) {} 的所有判断都是不成立的;
	   		 j          k         nums[i] + nums[j] + nums[k] 与 sum 关系            j++        k--  
			 7    <     9         nums[6]+nums[7]+nums[9] = 7+8+10 > 15                         8   
			 7    <     8         nums[6]+nums[7]+nums[8] = 7+8+9 > 15                          7
			 7    <     7     while (j < k) {} 不成立，循环结束;  



	第一个循环：for (let i = 0; i < len - 2; i++) {}, len = 10, i=7，j=i+1=8, k=len-1=9, sum = 15 的情况：
	    且在 i=7 的情况下，类似 if (i > 0 && nums[i] === nums[i - 1]) {} 的所有判断都是不成立的;
	   		 j          k         nums[i] + nums[j] + nums[k] 与 sum 关系            j++        k--  
			 8    <     9         nums[7]+nums[8]+nums[9] = 8+9+10 > 15                         8   
			 8    <     8     while (j < k) {} 不成立，循环结束;



	此时第一个循环就结束了：		
	此时的返回结果 res 为：[[1,4,10],[1,5,9],[1,6,8],[2,3,10],[2,4,9],[2,5,8],[2,6,7],[3,4,8],[3,5,7],[4,5,6]];	   


			 

其二、截图为：

ⅱ、小结：

其一、哪里有不对或不合适的地方，还请大佬们多多指点和交流！
其二、若有转发或引用本文章内容，请注明本博客地址(直接点击下面 url 跳转) ,创作不易，且行且珍惜！
其三、有兴趣的话，可以多多关注这个专栏(vue(vue2+vue3)面试必备专栏)(直接点击下面 url 跳转)：