简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
- Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ? b ? c ? d)
- The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
» Solve this problemThe Key point in this problem is to iterate through the list, completely and avoid duplication.
I set 4 pointers here, first of all, to be sure of 2 elements, and then go though to find the target value of moving other two elements. And what we need to pay attention is to avoid duplication. I use a hashmap here to store the result I already found. I translate the value to string first, then store in the hashmap.
nice job , however , your second solution ,the one without hashmap avoid repeating , at the end of method while(j<num.size()&&num[j]==num[j+1]) j++;
ReplyDelete}
while(i<num.size()&&num[i]==num[i+1]) i++;
here may throw some exception . if i<num.size, then num[i +1] the index will overflow out of the array . I use java , but I am sure if it's ok in c++. Nice blog btw!!
Nice code!
ReplyDeleteOne minor issue is that you concat the 4 numbers into a string and use it as the key to check the duplicated scenario in the hashmap, hm.count(str).
I think you should also prove the there are no two quadruples and can be concat into the same string. <1,12,34,56> or <11, 2, 34, 56>