算法题/双指针：最小和的三数

题目

给定一个未排序的数组arr和一个目标和，计算其中的所有三联体，使arr[i] + arr[j] + arr[k]<target，i j k是三个不同的索引。写一个函数返回这样的三元组的个数。

相似问题 ：写一个函数返回所有这样的三元组的列表，而不是计数。在这种情况下，时间复杂度将如何变化

示例1：

输入：[-1, 0, 2, 3], target=3
输出：2
解释：[-1, 0, 3], [-1, 0, 2]是最靠近3的2个三元组

示例2：

输入：[-1, 4, 2, 1, 3], target=5
输出：4
解释：[-1, 1, 4], [-1, 1, 3], [-1, 1, 3], [-1, 2, 3]是最靠近5的4个三元组

解答1：

Java

import java.util.*;

class TripletWithSmallerSum {

  public static int searchTriplets(int[] arr, int target) {
    Arrays.sort(arr);
    int count = 0;
    for (int i = 0; i < arr.length - 2; i++) {//外层循环，遍历数组，取第一个数
      count += searchPair(arr, target - arr[i], i);
    }
    return count;
  }

  //left指针和right指针组成的数对
  private static int searchPair(int[] arr, int targetSum, int first) {
    int count = 0;
    int left = first + 1, right = arr.length - 1;
    while (left < right) {//内存循环，找到符合条件的数对
      if (arr[left] + arr[right] < targetSum) { //找到三元组
        //由于arr[right] >= arr[left],所以我们能将arr[right]替换成 
        //left到right之间的任何一个数来得到三数之和小于target sum
        count += right - left;//left这个数 和 left+1到right之间的数组成的right
        left++;
      } else {
        right--; //向左移动right指针，从而得到更小的数对
      }
    }
    return count;
  }

  public static void main(String[] args) {
    System.out.println(TripletWithSmallerSum.searchTriplets(new int[] { -1, 0, 2, 3 }, 3));
    System.out.println(TripletWithSmallerSum.searchTriplets(new int[] { -1, 4, 2, 1, 3 }, 5));
  }
}

JavaScript

function searchTriplets(arr, target) {
  arr.sort((a, b) => a - b);
  let count = 0;
  for (let i = 0; i < arr.length - 2; i++) {
    count += searchPair(arr, target - arr[i], i);
  }
  return count;
}

function searchPair(arr, targetSum, first) {
  let count = 0;
  let left = first + 1;
  let right = arr.length - 1;
  while (left < right) {
    if (arr[left] + arr[right] < targetSum) {
      count += right - left;
      left++;
    } else {
      right--;
    }
  }
  return count;
}

console.log(searchTriplets([-1, 0, 2, 3], 3));
console.log(searchTriplets([-1, 4, 2, 1, 3], 5));

Python

def searchTriplets(arr, target):
    arr.sort()
    count = 0
    for i in range(len(arr) - 2):
        count += searchPair(arr, target - arr[i], i)
    return count


def searchPair(arr, targetSum, first):
    count = 0
    left = first + 1
    right = len(arr) - 1
    while left < right:
        if arr[left] + arr[right] < targetSum:
            count += right - left
            left += 1
        else:
            right -= 1
    return count


print(searchTriplets([-1, 0, 2, 3], 3))
print(searchTriplets([-1, 4, 2, 1, 3], 5))

Go

package main

import (
	"fmt"
	"sort"
)

func searchTriplets(arr []int, target int) int {
	sort.Ints(arr)
	count := 0
	for i := 0; i < len(arr)-2; i++ {
		count += searchPair(arr, target-arr[i], i)
	}
	return count
}

func searchPair(arr []int, targetSum, first int) int {
	count := 0
	left := first + 1
	right := len(arr) - 1
	for left < right {
		if arr[left]+arr[right] < targetSum {
			count += right - left
			left++
		} else {
			right--
		}
	}
	return count
}

func main() {
	fmt.Println(searchTriplets([]int{-1, 0, 2, 3}, 3))
	fmt.Println(searchTriplets([]int{-1, 4, 2, 1, 3}, 5))
}