脸家加面，似乎他家最近新题很多？

backtrack + dfs解法，算是subset的变种题把
void dfs(vector<int> nums, int idx, int &res, vector<int> &cur, int target)
{
    if(idx == nums.size())
    {
        return;
    }
    else
    {
        for(int i = idx; i < nums.size(); i++)
        {
            cur.push_back(nums[i]);
            if((cur.size() == 1 && cur[0] < target) || (cur[0] + cur.back() < target))
            {
                for(auto it : cur)
                {
                    cout<<it<<" ";
                }
                cout<<endl;
                res++;
                dfs(nums, i + 1, res, cur, target);
            }
            cur.pop_back();
            while(i < nums.size() - 1 && nums[i] == nums[i + 1])i++;
        }
    }
}
int count(vector<int> nums, int target)
{
    int res = 0;
    vector<int> cur;
    dfs(nums, 0, res, cur, target);
    return res;
}

int main()
{
    vector<int> nums = {2, 2, 3, 5, 7};
    cout<<count(nums, 8)<<endl;
   
}

补充内容 (2017-8-4 10:30):
if condition里(cur.size() == 1 && cur[0] < target) 条件去掉才对

twosumii 发表于 2017-8-4 07:27
并不是新题，你刷的不够 >

应该是 while i <= j  ？
while i < j 的时候结果会少了一个[3] （比如用LZ给的例子）

mingzhou1987 发表于 2017-8-4 08:54
楼主第二题，result得加上5和7.

[5] 和 [7] 不满足条件吧？最大最小值都是本身，相加大于K了

楼主加面是电面后还是onsite后的加面啊？

LZ这都是原题 :(

楼主
第一题如果用two pointer的话，题目的两个数组应该是sorted的吧？
假如没sort好是不是用hashmap 或 hashset 才会比较好？

补充内容 (2017-8-4 10:11):
第二题应该就是用two pointer吧？两层循环＝》O(n^2)

补充内容 (2017-8-4 10:16):
不对  第二题想了一想  O(n)应该就可以解出来了

flgt2014 发表于 2017-8-4 09:19
[5] 和 [7] 不满足条件吧？最大最小值都是本身，相加大于K了

我理解有误，sorry，楼主的例子是对的

twosumii 发表于 2017-8-4 07:27
并不是新题，你刷的不够 >

two pointers 正解。 不过 while 条件我觉得应该是i <= j， 不然会漏掉单一元素的子集。

res = 0
i, j = 0, len(s)-1
while i <= j:
    if s[i] ＋s[j] < k:
        res += pow(2, j-i)
        i += 1
    else:
        j -= 1
return res

如果用夹击求2次幂的解法遇到重复元素怎么破？譬如这个例子，{2, 3, 3, 5, 5, 7, 7} target为8，
2和5 range之间有两个3，如果都只包含一个3的子集，只能算一个

mingzhou1987 发表于 2017-8-4 11:48
如果用夹击求2次幂的解法遇到重复元素怎么破？譬如这个例子，{2, 3, 3, 5, 5, 7, 7} target为8，
2和5 ran ...

如果你实在想双指针，那么就先预处理把重复去掉咯。。。