首页 > 试题广场 > 给定一个整数数组,判断其中是否有3个数和为N
[编程题]给定一个整数数组,判断其中是否有3个数和为N
给定一个整数数组,判断其中是否有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 回复(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)
# -*- 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)

热门推荐

通过挑战的用户

查看代码