首页 > 试题广场 > 给定一个整数数组,判断其中是否有3个数和为N
[编程题]给定一个整数数组,判断其中是否有3个数和为N
  • 热度指数:1902 时间限制: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)
//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)
#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)
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)
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)
//不仅仅判断是否可以存在;倘若存在还可以对输出结果去重。借鉴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)

热门推荐

通过挑战的用户

查看代码