{"action":"opened","issue":{"url":"https://api.github.com/repos/niuworld/LeetCodeSolution/issues/19","labels_url":"https://api.github.com/repos/niuworld/LeetCodeSolution/issues/19/labels{/name}","comments_url":"https://api.github.com/repos/niuworld/LeetCodeSolution/issues/19/comments","events_url":"https://api.github.com/repos/niuworld/LeetCodeSolution/issues/19/events","html_url":"https://github.com/niuworld/LeetCodeSolution/issues/19","id":83990944,"number":19,"title":"18.4Sum","user":{"login":"niuworld","id":10355124,"avatar_url":"https://avatars.githubusercontent.com/u/10355124?v=3","gravatar_id":"","url":"https://api.github.com/users/niuworld","html_url":"https://github.com/niuworld","followers_url":"https://api.github.com/users/niuworld/followers","following_url":"https://api.github.com/users/niuworld/following{/other_user}","gists_url":"https://api.github.com/users/niuworld/gists{/gist_id}","starred_url":"https://api.github.com/users/niuworld/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/niuworld/subscriptions","organizations_url":"https://api.github.com/users/niuworld/orgs","repos_url":"https://api.github.com/users/niuworld/repos","events_url":"https://api.github.com/users/niuworld/events{/privacy}","received_events_url":"https://api.github.com/users/niuworld/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2015-06-02T12:02:24Z","updated_at":"2015-06-02T12:02:24Z","closed_at":null,"body":"### Question:\r\n>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.\r\n\r\n>Note:\r\n>Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)\r\n>The solution set must not contain duplicate quadruplets.\r\n>   For example, given array S = {1 0 -1 0 -2 2}, and target = 0.\r\n\r\n> A solution set is:\r\n>  (-1,  0, 0, 1)\r\n>  (-2, -1, 1, 2)\r\n>  (-2,  0, 0, 2)\r\n\r\n### Solution:\r\n```C++\r\nclass Solution {\r\npublic:\r\nvector<vector<int>> fourSum(vector<int>& nums, int target) {\r\n    sort( nums.begin(), nums.end());\r\n    vector<vector<int>>result;\r\n    vector<int>res;\r\n    int i, j, k, l;\r\n    int len = nums.size();\r\n    for( i = 0; i <= len - 4 ; ++i){\r\n        for( j = i + 1; j <= len - 3; ++j){\r\n            if( nums[i] + nums[j] > target && nums[j] >= 0)\r\n                break ;\r\n            k = j + 1;\r\n            l = len - 1;\r\n            while( k < l){\r\n                res.clear();\r\n                int minus = nums[i] + nums[j] + nums[k] + nums[l] - target;\r\n                if ( minus == 0){\r\n                    res.push_back(nums[i]);\r\n                    res.push_back(nums[j]);\r\n                    res.push_back(nums[k]);\r\n                    res.push_back(nums[l]);\r\n                    result.push_back(res);\r\n                    while ( nums[k+1] == nums[k]) k++;\r\n                    while ( nums[l-1] == nums[l]) l--;\r\n                    k++;\r\n                    l--;\r\n                }\r\n                else {\r\n                    if( minus > 0 )\r\n                    {           \r\n                             l--;\r\n                        while ( nums[l+1] == nums[l]) l--;\r\n                    }\r\n                    if( minus < 0)\r\n                    {\r\n                        k++;\r\n                        while ( nums[k-1] == nums[k]) k++;\r\n                    }\r\n               }\r\n            }\r\n            while( nums[j+1] == nums[j]) j++;\r\n        }\r\n        while( nums[i+1] == nums[i]) i++;\r\n    }\r\n    return result;\r\n  }\r\n};\r\n```\r\n"}}