Golang by Priority Queue
Intuition\n Describe your first thoughts on how to solve this problem. \nUsing same method from https://leetcode.com/problems/find-the-k-sum-of-an-array/solutio
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUsing same method from https://leetcode.com/problems/find-the-k-sum-of-an-array/solutions/2456716/python3-heap-priority-queue-o-nlogn-klogk/\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse Priority Queue to solve this problem.\n\n# Complexity\n- Time complexity: O(NlogN + klogk)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N + k)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\ntype KSumItem struct {\n\tSum   int64\n\tIndex int\n}\n\ntype PQ []KSumItem\n\nfunc (m PQ) Len() int { return len(m) }\nfunc (m PQ) Less(i, j int) bool {\n\treturn m[i].Sum > m[j].Sum\n}\nfunc (m PQ) Swap(i, j int)       { m[i], m[j] = m[j], m[i] }\nfunc (m *PQ) Push(x interface{}) { *m = append(*m, x.(KSumItem)) }\nfunc (m *PQ) Pop() interface{} {\n\told := *m\n\tn := len(old)\n\tx := old[n-1]\n\t*m = old[0 : n-1]\n\treturn x\n}\n\nfunc kSum(nums []int, k int) int64 {\n\tmaxSum := int64(0)\n\tfor i := range nums {\n\t\tif nums[i] >= 0 {\n\t\t\tmaxSum += int64(nums[i])\n\t\t} else {\n\t\t\tnums[i] = -nums[i]\n\t\t}\n\t}\n\tsort.Ints(nums)\n\n\tmaxHeap := make(PQ, 0)\n\tvar nextSum int64\n\theap.Push(&maxHeap, KSumItem{maxSum - int64(nums[0]), 0})\n\tnextSum = maxSum\n\tfor ; k > 1; k-- {\n\t\tnum := heap.Pop(&maxHeap).(KSumItem)\n\t\tnextSum = num.Sum\n\t\ti := num.Index\n\t\tif i+1 < len(nums) {\n\t\t\theap.Push(&maxHeap, KSumItem{nextSum + int64(nums[i]) - int64(nums[i+1]), i + 1})\n\t\t\theap.Push(&maxHeap, KSumItem{nextSum - int64(nums[i+1]), i + 1})\n\t\t}\n\t}\n\treturn nextSum\n}\n\n```
['Go']