不重复打印排序数组中相加和为给定值的所有三元组_

Java

pein531

固定第一个数，后两个数用双指针法得到，在移动指针的时候记得与前一次指针所指的数对比，两者不能相等。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]);
        params = br.readLine().split(" ");
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) nums[i] = Integer.parseInt(params[i]);
        for(int i = 0; i < n - 2; i++){
            if(i > 0 && nums[i] == nums[i - 1]) continue;     // 第一元素去重
            int target = k - nums[i];
            int left = i + 1;
            while(nums[left] == nums[i] && left < n - 1) left ++;       // 第二个元素不能等于第一个元素
            int right = n - 1;
            while(left < right){
                if(nums[left] + nums[right] > target){
                    right --;
                }else if(nums[left] + nums[right] < target){
                    left ++;
                }else{
                    if(nums[left] < nums[right]) System.out.println(nums[i] + " " + nums[left] + " " + nums[right]);
                    left ++;
                    right --;
                    while(nums[left] == nums[left - 1]) left ++;         // 第二元素去重
                    while(nums[right] == nums[right + 1]) right --;      // 第三元素去重
                }
            }
        }
    }
}

发表于 2021-11-19 16:41:06 回复(0)

爆米

数据有点坑...

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> v(N);
    for (int i = 0; i < N; ++i) {
        cin >> v[i];
    }
    for (int i = 0; i < N - 2; ++i) {
        if (i == 0 || v[i] != v[i - 1]) {
            int L = i + 1, R = N - 1;
            while (L < R) {
                ll sum = v[i] + v[L] + v[R];
                if (sum == K) {
                    // if (L == i + 1 || v[L] != v[L-1])
                    // 这题神坑，答案不允许前两个数字相同？？？
                    if (v[L] != v[L-1])
                        cout << v[i] << " " << v[L] << " " << v[R] << endl;
                    L += 1;
                    R -= 1;
                } else if (sum < K) {
                    L += 1;
                } else {
                    R -= 1;
                }
            }
        }
    }
    return 0;
}

发表于 2020-09-06 15:34:40 回复(0)

卖报人

#include<bits/stdc++.h>
using namespace std;

//这个要求了三元组前两个元素不相等才行（或者题目想说升序三元组？）
int main() {
    int N;
    cin>>N;
    long long k;
    cin>>k;
    int i;
    long long a[N];
    long long target, res, nowl, nowr;
    int l, r;
    for(i = 0; i < N; i++) {
        cin>>a[i];
    }
    
    for(i = 0; i < N-2; i++) {
        if(i > 0 && a[i] == a[i-1]){
            continue;
        }
        target = k - a[i];
        l = i+1;
        r = N-1;
        while(a[l] == a[i] && l < r) {
            l++;
        }
        
        while(l < r) {
            res = a[l] + a[r];
            if(res == target) {
                cout<<a[i]<<" "<<a[l]<<" "<<a[r]<<endl;
                nowl = a[l];
                nowr = a[r];
                while(a[l] == nowl && l < r) {
                    l++;
                }
                while(a[r] == nowr && l < r) {
                    r--;
                }
            }
            else if(res < target) {
                nowl = a[l];
                while(a[l] == nowl && l < r) {
                    l++;
                }
            }
            else {
                nowr = a[r];
                while(a[r] == nowr && l < r) {
                    r--;
                }
            }
        }
    }
    
    return 0;
}

/*
//这个写法才是不降序三元组，但是通不过= =
int main() {
    int N;
    cin>>N;
    long long k;
    cin>>k;
    int i;
    long long a[N];
    long long target, res, nowl, nowr;
    int l, r;
    for(i = 0; i < N; i++) {
        cin>>a[i];
    }
    
    for(i = 0; i < N-2; i++) {
        if(i > 0 && a[i] == a[i-1]){
            continue;
        }
        target = k - a[i];
        l = i+1;
        r = N-1;
        while(l < r) {
            res = a[l] + a[r];
            if(res == target) {
                cout<<a[i]<<" "<<a[l]<<" "<<a[r]<<endl;
                nowl = a[l];
                nowr = a[r];
                while(a[l] == nowl && l < r) {
                    l++;
                }
                while(a[r] == nowr && l < r) {
                    r--;
                }
            }
            else if(res < target) {
                nowl = a[l];
                while(a[l] == nowl && l < r) {
                    l++;
                }
            }
            else {
                nowr = a[r];
                while(a[r] == nowr && l < r) {
                    r--;
                }
            }
        }
    }
    
    return 0;
}
*/

编辑于 2020-03-01 15:09:45 回复(1)

20181123

n,target = list(map(int, input().split()))
arr = list(map(int, input().split()))
i = 0
result = []
while i < n-3:
#    故意把两个相同的元素过滤掉后，通过了编译
#--------------------------------------
    while arr[i] == arr[i+1]:
        i += 1
# -------------------------------------
    j = i + 1
    k = n-1
    temp = target-arr[i]
    while j < k:
        if arr[j] + arr[k] == temp:
#             result.append([arr[i],arr[j],arr[k]])
            print(arr[i],arr[j],arr[k])
            while arr[j] == arr[j+1]:
                j += 1
            while arr[k] == arr[k-1]:
                k -= 1
            j += 1
        elif arr[j] + arr[k] <temp:
            j += 1
        else:
            k -= 1
#-------------------------------------------
# 放在这反而不正确
#    while arr[i] == arr[i+1]:
#        i += 1
# ------------------------------------------
    i +=1

题目存在问题，没有考虑到，2+2+6 == 10这种情况。

发表于 2019-08-15 15:10:21 回复(1)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    cin>>n>>k;
    if(n<1)
        cout<<0<<endl;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n-3;i++){
        if(i==0 || a[i]!=a[i-1]){
            int t = k-a[i];
            int l=i+1, r=n-1;
            while(l<r){
                if(a[l]+a[r]==t){
                    if(a[l]!=a[l-1])
                        cout<<a[i]<<" "<<a[l]<<" "<<a[r]<<endl;
                    l++;
                    r--;
                }else if(a[l]+a[r]<t)
                    l++;
                else
                    r--;
            }
        }
    }
    return 0;
}

发表于 2020-01-29 01:01:34 回复(2)

张二狗1

为什么通不过，求指教，谢谢
import java.util.Scanner;
public class Main{
      public static void main(String[]  args){
          Scanner s=new Scanner(System.in);
          int n=s.nextInt();
          int k=s.nextInt();
          int arr[]=new int[n];
          for(int i=0;i<n;i++){
            arr[i]=s.nextInt();  
          }
          s.close();
          //至少要有三个数
          for(int i=0;i<arr.length-3;i++){
              //防重
              if(i>0&&arr[i]==arr[i-1]){
                  continue;
              }
              find(arr,i,k-arr[i]);
          }
          
      }
    //这就变成了用双指针查找数组中二元组一样的问题
    public static  void find(int arr[],int l,int k){
                 int left=l+1;
        int right=arr.length-1;
        while(left<right){
            if(arr[left]+arr[right]<k){
                left++;
            }else if(arr[left]+arr[right]>k){
                right--;
            }else{
                if(arr[left]==0||arr[left-1]!=arr[left]){
                    System.out.println(arr[l]+" "+arr[left]+" "+arr[right]);
                }
            }
        }
    }
}

发表于 2019-08-22 11:33:37 回复(5)

巨白龙

固定一个数a，目标变成了k-a，双标志向中间靠近

发表于 2019-08-20 09:13:36 回复(2)

不傲娇

上一题为 求出不重复的二元组
在本题中，我们只需要限定三元组中第一个数，后两个数就跟上一题一摸一样
重点一：
        去掉重复，我们保证不重复的二元组的同时，也要保证第一个数不一致

#include<iostream>
#include<vector>

using namespace std;

void printtraid(vector<int>&  vec,int start,int n,int k)
{
    int l=start+1,r=n-1;
    while(l<r)
    {
        if((vec[l]+vec[r])==k)
        {
            //cout<<"vec[l] "<<"vec[r]"<<endl;
            if(l==0||vec[l]!=vec[l-1]) //确保输出不重复且不会溢出
            {
                printf("%d %d %d\n",vec[start],vec[l],vec[r]);
            }
            r--;
            l++;
        }
        else if((vec[l]+vec[r])<k)
        {
            l++;
        }
        else{
            r--;
        }
    }
}


int main()
{
    int n,k,fin;
    cin>>n>>k;
    //scanf("%d,%d",&n,&k);
    vector<int> vec(n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&vec[i]);
    }
    int l=0,r=n-1,min;
    for(int i=0;i<n-2;i++)
    {
        if(i==0||vec[i]!=vec[i-1])//去重复
        {
            fin=k-vec[i];
            printtraid(vec,i,n,fin);
        }

    }

    return 0;
}

发表于 2020-12-28 19:36:43 回复(0)

Java

牛客135290605号

import java.util.*;
public class Main {
    public static void main(String[]args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        int arr[] = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = scanner.nextInt();
        int l = 0;
        int r = n - 1;
        int m = l + 1;
        while (l < r - 1) {
            //l++;
            if (l == 0 || arr[l] != arr[l - 1]) {
                //l不重复在比较m,r
                m = l + 1;
                r = n - 1;
                while (m < r) {
                    if (arr[l] + arr[m] + arr[r] == k) {
                        if ((m == 0 || arr[m] != arr[m - 1]) & arr[m] != arr[r])
                            System.out.println(arr[l] + " " + arr[m] + " " + arr[r]);
                        m++;
                        r--;
                    } else if (arr[l] + arr[m] + arr[r] < k)
                        m++;
                    else r--;
                }
            }
            l++;
        }
    }
}

发表于 2022-06-08 07:55:10 回复(0)

Java

牛客235394036号

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int K = sc.nextInt();
        int []arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        printByOrder(K , arr);
    }

    private static void printByOrder(int k, int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (i >= 1 &&arr[i] == arr[i - 1]) continue;
            int left = i + 1;
            int right = arr.length - 1;
            while(left < right){
                if (arr[i] + arr[left] + arr[right] < k) left ++;
                else if (arr[i] + arr[left] + arr[right] > k) right--;
                else {
                    if (arr[left] != arr[right] && arr[left] != arr[left -1]){
                        System.out.println(arr[i] + " " + arr[left] + " " + arr[right]);
                    }
                    left ++;
                    right--;
                }
            }
        }
    }
}

发表于 2022-05-25 15:38:46 回复(0)

青春的律动

public class Main {
    public static void printUniqueTriad(int[] arr, int k) {
        if (arr == null || arr.length < 3) {
            return;
        }
        for (int i = 0; i < arr.length - 2; i++) {
            if (i == 0 || arr[i] != arr[i - 1]) {
                printRest(arr, i, i + 1, arr.length - 1, k - arr[i]);
            }
        }
    }

    public static void printRest(int[] arr, int f, int l, int r, int k) {
        while (l < r) {
            if (arr[l] + arr[r] < k) {
                l++;
            } else if (arr[l] + arr[r] > k) {
                r--;
            } else {
                if (l == f + 1 || arr[l - 1] != arr[l]) {
                    System.out.println(arr[f] + " " + arr[l] + " " + arr[r]);
                }
                l++;
                r--;
            }
        }
    }

    public static void main(String[] args) {
        int sum = 10;
        int[] arr1 = { -8, -4, -3, 0, 1, 2, 4, 5, 8, 9 };
        printUniqueTriad(arr1, sum);

    }

}

发表于 2022-04-24 09:57:05 回复(0)

Python 3

阿司匹林Yo

def getRes(arr, n, k):
    if not arr:
        return
    # arr[i]代表三元组中第一个数字
    for i in range(n):
        # 去除重复数字
        if i > 0 and arr[i] == arr[i-1]:
            continue

        # 双指针搜索符合条件的二元组
        l, r = i+1, n-1
        while l < r:
            while l < r and l > i+1 and arr[l] == arr[l-1]:
                l += 1
            while l < r and r < n-1 and arr[r] == arr[r+1]:
                r -= 1
            if l >= r:
                break

            if arr[i] + arr[l] + arr[r] == k:
                if arr[i] < arr[l] < arr[r]:
                    print("{} {} {}".format(arr[i], arr[l], arr[r]))
                l, r = l+1, r-1
            elif arr[i] + arr[l] + arr[r] < k:
                l += 1
            else:
                r -= 1


if __name__ == '__main__':
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    getRes(arr, n, k)

发表于 2021-12-27 10:53:55 回复(0)

C++

麦芒2021

注意本题要求三个数严格升序

#include "iostream"
#include "vector"

using namespace std;
int main()
{
    int len,target;
    cin>>len;cin>>target;
    vector<int> arr(len);
    for(int i=0;i<len;i++)
    {
        cin>>arr[i];
    }
    int i,j,k,tmp;
    for(int i=0;i<len-2;i++)
    {
        if(i>0&&(arr[i]==arr[i-1])) continue;
        //for(j=i+1,k=len-1;j<k;j)
        j=i+1;
        k=len-1;
        while(j<k)
        {
            if((j>=i+1)&&(arr[j]==arr[j-1])){j++;continue;}//用>=保证严格升序
            if((k<len-1)&&(arr[k]==arr[k+1])){k--;continue;}
            if(arr[j]==arr[k]){break;}//保证严格升序
            tmp=arr[i]+arr[j]+arr[k];
            if(tmp==target){cout<<arr[i]<<' '<<arr[j]<<' '<<arr[k]<<endl;j++;k--;}
            else if(tmp>target){k--;}
            else {j++;}
        }
    }
    return 0;
}

发表于 2021-12-26 12:05:33 回复(0)

牛客79631828号

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(print3Nums(arr, k));
    }
    
    public static String print3Nums (int[] arr, int k) 
    {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length - 2; i++) {
            //保证第一个数不会被重复打印
            if (i == 0 || arr[i] != arr[i-1])
                print2Nums(arr, i, i+1, arr.length-1, k - arr[i], sb);
        }
        return sb.toString();
    }
    
    public static void print2Nums(int[] arr, int i, int start, 
                                  int end, int sum, StringBuilder sb) {
        int left = start;
        int right = end;
        while (left < right) {
            if (arr[left] + arr[right] > sum)
                right--;
            else if (arr[left] + arr[right] < sum)
                left++;
            else {
                //保证接下来的两个数不会被重复打印
                if (left == 0 || arr[left] != arr[left-1])
                    sb.append(arr[i] + " " + arr[left] + " " + arr[right] + "\n");
                left++;
                right--;
            }
        }
    }
}

发表于 2021-08-19 15:55:33 回复(0)

UncleFly

#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
void printRest(vector<LL>& arr, int start, int left, int right, LL k){
    k -= arr[start];
    int n = arr.size();
    int l = left, r = right;
    while(l<r){
        LL sum = arr[l] + arr[r];
        if(sum == k){
            if((l==left||arr[l]!=arr[l-1])&&arr[start]<arr[l])
                //数据有点问题，严格递增的三元组应该再加上arr[l]< arr[r]的条件. 去掉这个条件就能ac
                cout<<arr[start]<<" "<<arr[l]<<" "<<arr[r]<<endl;
            l++;
            r--;
        }else if(sum < k){
            l++;
        }else{
            r--;
        }
    }
}

int main(){
    int n;
    LL k;
    cin>>n>>k;
    vector<LL> arr(n, 0);
    for(int i = 0;i<n;i++)
        cin>>arr[i];
    for(int i = 0;i<n;i++)
    {
        if(i==0||arr[i]!=arr[i-1])
            printRest(arr, i, i+1, n-1, k);
    }
    return 0;
}

发表于 2021-06-08 21:01:56 回复(0)

MarcoMayCry

数据有问题，题目明明要求严格升序，但是答案后两位可重复，前两位不可以，有毒

发表于 2021-03-15 18:19:14 回复(0)

lishangru

帮忙看看代码有问题嘛？通过率0%，力扣写了编能过的

def printTriplets():
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    for i in range(n - 2):
        if i > 0 and arr[i] == arr[i - 1]:
            continue
        tar = k - arr[i]
        if tar < arr[i + 1] + arr[i + 2] or tar > arr[n - 1] + arr[n - 2]:
            continue
        j, l = i + 1, n - 1
        while j < l:
            if j > i + 1 and arr[j] == arr[j - 1]:
                j += 1
                continue
            if arr[j] + arr[l] == tar:
                print(arr[i], arr[j], arr[l])
                j += 1
            elif arr[j] + arr[l] > tar:
                l -= 1
            else:
                j += 1

printTriplets()

编辑于 2020-12-26 18:37:16 回复(0)

Ruoji55555

这数据可太假了。。。前两个数不能相同....

发表于 2020-11-07 14:31:20 回复(0)

Java

搬砖的醇香土豆泥

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int k = Integer.parseInt(s[1]);
        int[] mat = new int[n];
        s = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            mat[i] = Integer.parseInt(s[i]);
        }
        int[][] res = new int[n][3];
        int index = 0;
        for (int i = 0; i < n - 2; i++) {
            int curSum = k - mat[i];
            int lo = i + 1, hi = n - 1;
            while (lo < hi) {
                int val1 = mat[lo], val2 = mat[hi];
                if (mat[lo] + mat[hi] == curSum) {
                    res[index][0] = mat[i];
                    res[index][1] = mat[lo];
                    res[index][2] = mat[hi];
                    index++;
                    while (lo < hi && mat[lo] == val1) lo++;
                    while (lo < hi && mat[hi] == val2) hi--;
                } else if (mat[lo] + mat[hi] < curSum) {
                    while (lo < hi && mat[lo] == val1) lo++;
                } else {
                    while (lo < hi && mat[hi] == val2) hi--;
                }
            }
        }
        for (int i = 0; i < index; i++) {
            System.out.println(res[i][0] + " " + res[i][1] + " " + res[i][2]);
        }
    }
}

为什么报错说我数组越界？求解...

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 999

at Main.main(Main.java:22)

发表于 2020-09-18 20:15:34 回复(0)

Java

小吴..

跳过重复的数据果然通过了

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        for (int i = 0; i < n-1; i++){
            if (arr[i] == arr[i+1]){    //跳过重复的数
                continue;
            }
            solve(arr,i+1,arr.length-1,k-arr[i],arr[i]);
        }
    }

    public static void solve(int[] arr, int pre, int behind, int value, int now){
        int left = pre;
        int right = behind;
        while (left < right) {
            if (arr[left] + arr[right] == value) {
                while (arr[left] == arr[left + 1]) {
                    left++;
                }
                while (arr[right] == arr[right - 1]) {
                    right--;
                }
                System.out.println(now + " " + arr[left] + " " + arr[right]);
                left++;
                right--;
            } else if (arr[left] + arr[right] > value) {
                right--;
            } else {
                left++;
            }
        }
    }
}

发表于 2020-09-07 14:49:17 回复(0)

不重复打印排序数组中相加和为给定值的所有三元组

输入描述:

输出描述:

输入

输出

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题