PAT 解题报告 1048. Find Coins (25)

1048. Find Coins 题目描述:

经典的2sum问题, 给一个数组, 以及一个给定的值, 找到数组里面的两个值使得他们的和等于给定的值.

Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she could only use exactly two coins to pay the exact amount. Since she has as many as 105 coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find two coins to pay for it.

1048. Find Coins 算法分析:

这个题目就是换汤不换药了, 经典的2sum求和问题, 先给数组排序, 然后头尾指针分别从前后开始扫, 扫到的两个数的和若比给定的值要小, 那么头指针向后移动一步, 如果比给定的值大, 那么尾指针向前移动一步. 如果正好找到了, 那么就是他了, 返回.

其他其实还有诸如哈希的方法等等, 这个经典问题还有扩展K SUM, 可以参考我的博文”求和问题总结(leetcode 2Sum, 3Sum, 4Sum, K Sum)”, 在那里有比较多的讨论, 包括我自己的研究, 也有一些网友的讨论.

#include <cstdio>
#include <algorithm>
#include <vector>

#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;

vector<int> vals;

int main(void) {
    int N, M;
    scanf("%d %d", &N, &M);
    vals.resize(N);
    REP(i, N) scanf("%d", &vals[i]);
    int i=0;
    int j=N-1;
    sort(vals.begin(), vals.end());
    bool found = false;
    while(i < j) {
        int sum = vals[i] + vals[j];
        if(sum == M) {
            found = true;
            break;
        }
        else if(sum < M) {
            i++;
        }
        else
            j--;
    }
    if(found) {
        printf("%d %d\n", vals[i], vals[j]);
    }
    else {
        printf("No Solution\n");
    }
    return 0;
}
Written on January 19, 2014