首页 > 试题广场 >

给定一个整数数组,判断其中是否有3个数和为N

[编程题]给定一个整数数组,判断其中是否有3个数和为N
  • 热度指数:4284 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
给定一个整数数组,判断其中是否有3个数和为N

输入描述:
输入为一行
逗号前为一个整数数组,每个元素间用空格隔开;逗号后为N


输出描述:
输出bool值
True表示存在3个和为N的数
False表示不存在3个和为N的数
示例1

输入

1 2 3 4 5,10

输出

True

备注:
数组长度不超过2000,所以数均为int范围的正整数
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    vector<int>num;
    while(cin>>m)
    {
        if(getchar() == ',')
            break;
        num.push_back(m);
    }
    cin>>n;
    sort(num.begin(),num.end());
    for(int i=1;i<=num.size()-2;i++)
    {
        int first = 0;
        int last = num.size()-1;
        while(first<i && last>i)
        {
            if(num[first]+num[last]+num[i] == n)
            {
                cout << "True" << endl;
                return 0;
            }
            else if(num[first]+num[last]+num[i] < n)
                first++;
            else
                last--;
        }
    }
    cout << "False" << endl;
    return 0;
}

发表于 2019-07-23 08:38:21 回复(3)
while(line = readline()){
    var lines = line.split(",");
    var t = lines[0];
    var n = parseInt(lines[1]);
    var y = t.split(" ");
    var temp=[];
    for(i = 0;i<y.length;i++){
        temp.push(parseInt(y[i]));
    }
    temp.sort(com);
    var pp=yes(temp,n)
    print(pp)
}
function yes(temp,n){
        for(i=1;i<temp.length-2;i++){
        var first = 0;
        var last = temp.length-1;
        while(i>first&&i<last){
            if(temp[i]+temp[first]+temp[last]==n){
                var pp ="True";
                return pp;
            }
            else if(temp[i]+temp[first]+temp[last]<n){
                first++;
            }else{
                last--;
            }
        }
            var pp = "False"
    }
    return pp;
}
function com(a,b){
    return a-b;
}

发表于 2019-09-03 14:48:23 回复(0)
import java.util.*;
public class Main {
    public static void main(String[] args) {
        java.util.Scanner scanner = new java.util.Scanner(System.in);
        String str = scanner.nextLine();
        String[] temp = str.split(",");
        String[] numstr = temp[0].split(" ");
        int[] nums = new int[numstr.length];
        for (int i = 0; i < nums.length; i++)
            nums[i] = Integer.valueOf(numstr[i]);
        int target = Integer.valueOf(temp[1]);
        java.util.Arrays.sort(nums);
          
        for (int i = 0; i < nums.length - 2; i++) {
            int start = i + 1, end = nums.length - 1;
            while (start < end) {
                int sum = nums[i] + nums[start] + nums[end];
                if (sum == target){
                    System.out.println("True");
                    return;
                }  else if (sum < target)
                    start++;
                else
                    end--;
            }
        }
        System.out.println("False");
    }
}

编辑于 2019-08-20 15:46:26 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,x;
    vector<int> v;
    while(cin>>x){
        v.push_back(x);
        if(getchar()==',')
            break;
    }
    cin>>n;
    sort(v.begin(), v.end());
    int m=v.size(), l, r;
    for(int i=1;i<=m-2;i++){
        l = 0;
        r = m-1;
        while(l<i && r>i){
            if(v[l]+v[r]+v[i] == n){
                cout<<"True"<<endl;
                return 0;
            }else if(v[l]+v[r]+v[i] < n)
                l++;
            else
                r--;
        }
    }
    cout<<"False"<<endl;
    return 0;
}

发表于 2019-10-01 10:15:07 回复(0)
def main():
    m, n = input().split(',')
    m, n = list(map(int, m.split())), int(n)
    m.sort()
    if len(m) < 3:
        print("True")
        return
    for i in range(len(m) - 2):
        if i - 1 >= 0 and m[i] == m[i - 1]:
            continue
        j, k = i + 1, len(m) - 1
        while(j < k):
            res = m[j] + m[k] + m[i] - n
            if res > 0:
                k -= 1
            elif res < 0:
                j += 1
            else:
                print("True")
                return
    print("False")
if __name__ == "__main__":
    main()


发表于 2019-09-20 09:36:04 回复(0)
# -*- coding:utf-8 -*-
def find(numbers,key):
    record = []
    dirc = {}
    for i in range(len(numbers)): #用哈希表换来O(n^2)的时间复杂度
        if key-numbers[i] in dirc:
            dirc[key-numbers[i]] += [i]
        else:
            dirc[key-numbers[i]] = [i]
    for i in range(len(numbers)-1):
        for j in range(i+1,len(numbers)):
            if numbers[i] + numbers[j] in dirc:
                if i not in dirc[numbers[i] + numbers[j]] and j not in dirc[numbers[i] + numbers[j]]:
                    return True
    return False
if __name__=="__main__":
    num = input().split(",")
    numbers = [int(i) for i in num[0].split()]
    key = int(num[-1])
    print(find(numbers, key)) 

发表于 2019-07-04 11:10:54 回复(0)
//set双重遍历,查找第三个值
#include <bits/stdc++.h>
using namespace std;
int main(){
    set<int> num;
    set<int>::iterator i,j;
    bool flag=false;
    int n;
    while(1){
        int t;
        cin>>t;
        num.insert(t);
        if(cin.get()==','){
            cin>>n;
            break;
        }
    }
    for(i=num.begin();i!=num.end();i++){
        j=i;
        for(j++;j!=num.end();j++)
            if(num.find(n-*i-*j)!=num.end()){
                flag=true;
                break;
            }
    }
    cout<<(flag ? "True":"False");
    return 0;
}

发表于 2019-11-16 10:20:44 回复(0)
3层for循环暴力通过。。。
发表于 2020-08-05 15:29:02 回复(0)
const input = readline().split(',');
  const arr = input[0].split(' ').map((item) => +item);
  const n = +input[1];
  let findFlag = false;

  for(let i = 0; i < arr.length; i++) {
    if(findFlag) break;
    for(let j = i + 1; j < arr.length; j ++) {
      if(findFlag) break;
      for (let k = j + 1; k < arr.length; k++) {
        if (arr[i]+arr[j]+arr[k] === n) {
          findFlag=true;
          break;
        }
      }
    }
  }
  console.log(findFlag ? 'True' : 'False');

把评论区第一个解答转化为js后发现只能通过16个,不知道原因,故而还是用3重for解决, 用时1500ms

发表于 2021-09-03 22:11:21 回复(0)
看了一圈C组其他大佬们的多指针或者动态规划代码,很是敬佩。但作为小白,我也想简单分享一下自己的解法。
C语言解法:类似三指针思想。利用三重循环以及循环变量i,j,k分别从数组0号位开始遍历,其中i指向最前位,j指向下一位,k指向最后一位。三重循环遍历数组,如果存在3个循环变量之和等于求和数,则打印True并main函数返回0结束程序,否则循环结束后打印False并且结束。
#include<stdio.h>
#include<string.h>
int main()
{
    int a[2001]={0};
    int i=0,n=0,key=0,j,k;
    char c;
    while (scanf("%d",&a[i])!=EOF)
    {
        n++;
        i++;
        if((c=getchar())!=' ') break;
    }
    scanf("%d",&key);
    for(i=0;i<=n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            for(k=j+1;k<=n;k++)
            {
                if((a[i]+a[j]+a[k])==key)
                {
                    printf("True\n");
                    return 0;
                }
            }
        }
    }
    printf("False\n");
    return 0;
}


发表于 2021-08-19 10:47:18 回复(0)
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
    public  int[] StringToInt(String[] a){
        int res[]=new int[a.length];
        for (int i=0;i<a.length;i++){
            res[i]=Integer.parseInt(a[i]);
        }return  res;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
//        System.out.println("输入数组与目标数字:");
        String str=sc.nextLine();
        String [] strings=str.split(",");
        int res=Integer.parseInt(strings[1]);
        String [] arr=strings[0].split(" ");
        Main s=new Main();
        int []arrays= s.StringToInt(arr);
        boolean r=false;
      
        for (int i=0;i<arrays.length-2;i++){
            if(r){break;}
            int a=arrays[i];
            for (int j=i+1;j<arrays.length-1;j++){
                if(r){
                  break;
                }
                int b= arrays[j];
                for (int k=j+1;k<arrays.length;k++){
                    int c=arrays[k];
                    int sum= a+b+c;
                    if (sum==res){
                        System.out.println("True");
                        r=true;
                        break;
                    }
                    else if (i==arrays.length-3){
                        System.out.println("False");
                        r=true;
                        break;
                    }
                }
            }
        }

    }
   
}
发表于 2020-09-17 21:55:02 回复(0)
借助集合将复杂度降到n2,但耗时还是比较长。
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

/**
 * @Author: coderjjp
 * @Date: 2020-05-07 8:40
 * @Description:给定一个整数数组,判断其中是否有3个数和为N
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String ss[] = sc.nextLine().split(",");
        int N = Integer.valueOf(ss[1]);
        String[] s = ss[0].split(" ");
        int arr[] = new int[s.length];
        for (int i = 0; i < s.length; i++)
            arr[i] = Integer.valueOf(s[i]);
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i< s.length; i++){
            int target = N - arr[i];
            for (int j = 0; j < s.length; j++){
                if (j == i) continue;
                if (set.contains(target - arr[j])){
                    System.out.println("True");
                    return;
                }
                set.add(arr[j]);
            }
            set.clear();
        }
        System.out.println("False");
    }
}
比较好的方法是先排序,同样把三数和问题转化为两数和问题。
import java.util.Arrays;
import java.util.Scanner;

/**
 * @Author: coderjjp
 * @Date: 2020-05-07 11:56
 * @Description:
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String ss[] = sc.nextLine().split(",");
        int N = Integer.valueOf(ss[1]);
        String[] s = ss[0].split(" ");
        int arr[] = new int[s.length];
        for (int i = 0; i < s.length; i++)
            arr[i] = Integer.valueOf(s[i]);
        Arrays.sort(arr);
        int target, l, r;
        for (int i = 0; i < s.length - 2; i++){
            target = N -arr[i];
            l = i + 1;
            r = s.length - 1;
            while (l < r){
                if (arr[l] + arr[r] == target){
                    System.out.println("True");
                    return;
                }else if (arr[l] + arr[r] > target)
                    r--;
                else 
                    l++;
            }
        }
        System.out.println("False");
    }
}


编辑于 2020-05-07 12:06:26 回复(0)
3指针+剪枝
#include <iostream>
(720)#include <vector>
#include <cstdio>
(802)#include <algorithm>

#define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;


int main(void)
{
    vector<int> nums;
    int num;
    do
    {
        cin >> num;
        nums.push_back(num);
    }while((getchar()) == ' ');
    int target;
    cin >> target;
    sort(nums.begin(), nums.end());
    int n = nums.size();
    for(int i = 0; i < n - 2; i++)
    {
        if(i > 0 && nums[i - 1] == nums[i]) continue;
        if(nums[i] > target) break;
        if(nums[i] + nums[n - 1] + nums[n - 2] < target) continue;
        int ll = i + 1;
        int rr = n - 1;
        while(ll < rr)
        {
            int ssum = nums[i] + nums[ll] + nums[rr];
            if(ssum == target)
            {
                cout << "True" << endl;
                return 0;
            }
            else if(ssum < target)
            {
                while(ll < rr && nums[ll] == nums[ll + 1])
                    ll++;
                ll++;
            }
            else
            {
                while(ll < rr && nums[rr] == nums[rr - 1])
                    rr--;
                rr--;
            }
            
        }
    }
    cout << "False" << endl;
    return 0;
}


发表于 2020-04-15 18:50:48 回复(0)
import java.util.HashMap;
import java.util.Scanner;

public class FindNums {
    public String findNums(String[] nums,int target){
        HashMap<Integer,Integer> map=new HashMap<>();
        int[] num=new int[nums.length];
        for(int i=0;i<nums.length;i++){
            num[i]=Integer.parseInt(nums[i]);
            map.put(num[i],i);
        }
        for(int j=0;j<num.length;j++){
            int dif=target-num[j];
            for(int k=j+1;k<num.length;k++){
                int dif2=dif-num[k];
                if(map.get(dif2)!=null){
                  return "True";
                }
            }
        }
        return "False";
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            String scan=sc.nextLine();
            String[] tmpTest=scan.split(",");
            String[] num=tmpTest[0].split(" ");
            int nums=Integer.parseInt(tmpTest[1]);
            FindNums fn=new FindNums();
            String result=fn.findNums(num,nums);
            System.out.println(result);
        }
    }
}

发表于 2020-02-21 18:43:14 回复(1)
leetcode 原题 三数之和 四数之和,用双指针解决两个,其他用遍历
#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> nums;
    int target = 0;
    while(cin>>target)
    {
        nums.push_back(target);
        if(getchar()==',') break;
    }
    cin>>target;
    sort(nums.begin(), nums.end());
    for(int i=0; i<nums.size()-2; i++)
    {
        int l = i+1, r = nums.size()-1;
        int sum = target-nums[i];
        while(l<r)
        {
            if(nums[l]+nums[r]==sum)
            {
                cout<<"True"<<endl;
                return 0;
            }
            else if(nums[l]+nums[r]<sum) l++;
            else if(nums[l]+nums[r]>sum) r--;
        }
    }
    cout<<"False"<<endl;
    return 0;
}


发表于 2019-12-28 14:45:32 回复(0)
def sum3(data, value):
    if not data: return False
    data.sort()
    for i in range(len(data)):
        left, right = i + 1, len(data) - 1
        while left < right:
            res = data[i] + data[left] + data[right]
            if res == value:
                return True
            elif res > value:
                right -= 1
            else:
                left += 1
    return False

data, value = input().split(',')
data = list(map(int, data.split()))
value = int(value)
print(sum3(data, value))
转博文https://blog.csdn.net/zichen_ziqi/article/details/81417262
发表于 2019-10-09 16:47:22 回复(0)
用和N减去数组中的任意两个数,得到的差若还存在于数组中则说明存在这样三个数和为N,否则就不存在。
import java.util.HashMap;
import java.util.Scanner;
public class Main{
    public String sumN(String[]a,int N){
        HashMap map = new HashMap();
        for(int i=0;i<a.length;i++){
            map.put(Integer.parseInt(a[i]),i);            
        }
        for(int i=0;i<a.length;i++){
            int num1 = N - Integer.parseInt(a[i]);
            for(int j=i;j<a.length;j++){
                int num2 = num1-Integer.parseInt(a[j]);
                if(map.containsKey(num2)) return "True";
            }
        }
        return "False";
    }
    
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String[] temp = str.split(",");
        String[] numstr = temp[0].split(" ");
        int nums = Integer.parseInt(temp[1]);
        Main test = new Main();
        String result = test.sumN(numstr,nums);
        System.out.println(result);
    }
}
发表于 2019-09-10 15:07:23 回复(1)
#include<stdio.h>

void quicksort(int a[],int n)
{
    int i=0,j=n-1,m=a[0];
    while(i<j)
    {
        while(i<j&&a[j]>m) {j--;}
        if(i<j)
        {
            a[i]=a[j];
            i++;
        }
        while(i<j&&a[i]<m) {i++;}
        if(i<j)
        {
            a[j]=a[i];
            j--;
        }
    }
    a[i]=m;
    if(i>1) {quicksort(a,i);}
    if(n-i-1>1) {quicksort(a+i+1,n-i-1);}
}

int main()
{
    int a[2000];
    int i=0;
    char c;
    for(;i<2000;i++)
    {
        scanf("%d%c",&a[i],&c);
        if(c!=' ') {break;}
    }
    i++;
    scanf("%d%c",&a[i],&c);
    if(c!='\n')
    {
        printf("False\n");
        return 0;
    }

    quicksort(a,i);

    int ad,di,j=0;
    int *left,*right;
    _Bool eq=0;
    for(;j<i-2;j++)
    {
        left=&a[j+1];
        right=&a[i-1];
        di=a[i]-a[j];
        while(left<right)
        {
            ad=(*left)+(*right);
            eq=ad==di;
            if(eq) {break;}
            if(ad>di) {right--;}
            else {left++;}
        }
        if(eq) {break;}
    }
    if(eq) {printf("True\n");}
    else {printf("False\n");}

    return 0;
}
发表于 2019-09-10 10:11:00 回复(0)
;(function () {
        var line = readline().split(',')
        var arr = line[0].split(' ')
        var N = parseInt(line[1])

        arr = arr.map((e)=>{
            return parseInt(e)
        })
        arr.sort((a,b)=>{return a-b})
       
        for (var i = 1; i <= arr.length - 2;++i){
            var first = 0
            var last = arr.length - 1
            while (i>first&&i<last){
                if (arr[i]+arr[first]+arr[last]===N){
                    console.log('True')
                    return
                }else if (arr[i]+arr[first]+arr[last]<N){
                    first++
                }else{
                    last--
                }
            }
        }
        console.log('False')
    })()

发表于 2019-08-20 16:07:40 回复(0)
//不仅仅判断是否可以存在;倘若存在还可以对输出结果去重。借鉴leetcode 15 

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums, int N) {

		sort(nums.begin(), nums.end());
		vector<vector<int>> res;

		for (int i = 0; i < nums.size(); i++)
		{
			int target = N - nums[i];
			int first = i;
			int last = nums.size() - 1;

			if (target < 0)
			{
				break;
			}


			while (first < last)
			{
				int sum = nums[first] + nums[last];
				if (sum > target)
					last--;
				else if (sum < target)
					first++;
				else
				{
					vector<int> triplet(3, 0);
					triplet[0] = nums[i];
					triplet[1] = nums[first];
					triplet[2] = nums[last];
					res.push_back(triplet);

					while (first < last && nums[first] == triplet[1]) first++;
					while (last < last && nums[last] == triplet[2]) last--;
				}
			}
			while (i + 1 < nums.size() && nums[i + 1] == nums[i])  i++;
		}
		return res;
	}
};

int main()
{
	//vector<int> nums = { 2, 3, 2, 4, 1, 5, 6, 7, 8 };
	int N;
	int m;
	vector<int> nums;
	while (cin >> m)
	{
		if (getchar() == ',')
			break;
		nums.push_back(m);

	}
	cin >> N;
	Solution s;
	vector<vector<int>> res;
	res = s.threeSum(nums, N);
	if (res.empty())
	{
		cout << "False";
	}
	else
	{
		cout << "True";
	}
	return 0;
}

编辑于 2019-08-10 19:41:35 回复(0)

热门推荐

通过挑战的用户

查看代码