Browser tab content: Problem List
Register
or
Sign in
Premium
Debugging...
Run
Submit
Description
Editorial
Editorial
Solutions
Solutions
Submissions
Submissions
Code
Testcase
Test Result
Test Result
15. 3Sum
Medium
Topics
Companies
Hint

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

 

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.


Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.


Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.


 

Constraints:

3 <= nums.length <= 3000
-105 <= nums[i] <= 105
Accepted
4.1M
Submissions
11.5M
Acceptance Rate
35.7%
Topics
Array
Two Pointers
Sorting
Companies
Hint 1
So, we essentially need to find three numbers x, y, and z such that they add up to the given value. If we fix one of the numbers say x, we are left with the two-sum problem at hand!
Hint 2
For the two-sum problem, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y, which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?
Hint 3
The second train of thought for two-sum is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?
Similar Questions
Two Sum
Easy
3Sum Closest
Medium
4Sum
Medium
3Sum Smaller
Medium
Number of Arithmetic Triplets
Easy
Minimum Sum of Mountain Triplets I
Easy
Minimum Sum of Mountain Triplets II
Medium
Discussion (484)
Choose a type
Preview
Comment
💡 Discussion Rules

1. Please don't post any solutions in this discussion.

2. The problem discussion is for asking questions about the problem or for sharing tips - anything except for solutions.

3. If you'd like to share your solution for feedback and ideas, please head to the solutions tab and post it there.

Sort by:Best
No comments yet.
1
2
3
4
5
6
49
Copyright ©️ 2024 LeetCode All rights reserved
31.7K
484
556 Online
C++
Auto
1
2
3
4
5
6
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        
    }
};
Saved
Ln 4, Col 9
You need to Login / Sign up to run or submit
Case 1
Case 2
Case 3
nums =
[-1,0,1,2,-1,-4]
1
2
3
[-1,0,1,2,-1,-4]
[0,1,1]
[0,0,0]
Source

Problem List
Tag
1. Two Sum

Easy

2. Add Two Numbers

Med.

3. Longest Substring Without Repeating Characters

Med.

4. Median of Two Sorted Arrays

Hard

5. Longest Palindromic Substring

Med.

6. Zigzag Conversion

Med.

7. Reverse Integer

Med.

8. String to Integer (atoi)

Med.

9. Palindrome Number

Easy

10. Regular Expression Matching

Hard

11. Container With Most Water

Med.

12. Integer to Roman

Med.

13. Roman to Integer

Easy

14. Longest Common Prefix

Easy

15. 3Sum

Med.

16. 3Sum Closest

Med.

17. Letter Combinations of a Phone Number

Med.

18. 4Sum

Med.

19. Remove Nth Node From End of List

Med.

20. Valid Parentheses

Easy

21. Merge Two Sorted Lists

Easy

22. Generate Parentheses

Med.

23. Merge k Sorted Lists

Hard

24. Swap Nodes in Pairs

Med.

25. Reverse Nodes in k-Group

Hard

26. Remove Duplicates from Sorted Array

Easy

27. Remove Element

Easy

28. Find the Index of the First Occurrence in a String

Easy

29. Divide Two Integers

Med.

30. Substring with Concatenation of All Words

Hard

31. Next Permutation

Med.

32. Longest Valid Parentheses

Hard

33. Search in Rotated Sorted Array

Med.

34. Find First and Last Position of Element in Sorted Array

Med.

35. Search Insert Position

Easy

36. Valid Sudoku

Med.

37. Sudoku Solver

Hard

38. Count and Say

Med.

39. Combination Sum

Med.

40. Combination Sum II

Med.

41. First Missing Positive

Hard

42. Trapping Rain Water

Hard

43. Multiply Strings

Med.

44. Wildcard Matching

Hard

45. Jump Game II

Med.

46. Permutations

Med.

47. Permutations II

Med.

48. Rotate Image

Med.

49. Group Anagrams

Med.

50. Pow(x, n)

Med.

51. N-Queens

Hard

52. N-Queens II

Hard

53. Maximum Subarray

Med.

54. Spiral Matrix

Med.

55. Jump Game

Med.

56. Merge Intervals

Med.

57. Insert Interval

Med.

58. Length of Last Word

Easy

59. Spiral Matrix II

Med.

60. Permutation Sequence

Hard

61. Rotate List

Med.

62. Unique Paths

Med.

63. Unique Paths II

Med.

64. Minimum Path Sum

Med.

65. Valid Number

Hard

66. Plus One

Easy

67. Add Binary

Easy

68. Text Justification

Hard

69. Sqrt(x)

Easy

70. Climbing Stairs

Easy

71. Simplify Path

Med.

72. Edit Distance

Med.

73. Set Matrix Zeroes

Med.

74. Search a 2D Matrix

Med.

75. Sort Colors

Med.

76. Minimum Window Substring

Hard

77. Combinations

Med.

78. Subsets

Med.

79. Word Search

Med.

80. Remove Duplicates from Sorted Array II

Med.

81. Search in Rotated Sorted Array II

Med.

82. Remove Duplicates from Sorted List II

Med.

83. Remove Duplicates from Sorted List

Easy

84. Largest Rectangle in Histogram

Hard

85. Maximal Rectangle

Hard

86. Partition List

Med.

87. Scramble String

Hard

88. Merge Sorted Array

Easy

89. Gray Code

Med.

90. Subsets II

Med.

91. Decode Ways

Med.

92. Reverse Linked List II

Med.

93. Restore IP Addresses

Med.

94. Binary Tree Inorder Traversal

Easy

95. Unique Binary Search Trees II

Med.

96. Unique Binary Search Trees

Med.

97. Interleaving String

Med.

98. Validate Binary Search Tree

Med.

99. Recover Binary Search Tree

Med.

100. Same Tree

Easy

101. Symmetric Tree

Easy

102. Binary Tree Level Order Traversal

Med.

103. Binary Tree Zigzag Level Order Traversal

Med.

104. Maximum Depth of Binary Tree

Easy

105. Construct Binary Tree from Preorder and Inorder Traversal

Med.

106. Construct Binary Tree from Inorder and Postorder Traversal

Med.

107. Binary Tree Level Order Traversal II

Med.

108. Convert Sorted Array to Binary Search Tree

Easy

109. Convert Sorted List to Binary Search Tree

Med.

110. Balanced Binary Tree

Easy

111. Minimum Depth of Binary Tree

Easy

112. Path Sum

Easy

113. Path Sum II

Med.

114. Flatten Binary Tree to Linked List

Med.

115. Distinct Subsequences

Hard

116. Populating Next Right Pointers in Each Node

Med.

117. Populating Next Right Pointers in Each Node II

Med.

118. Pascal's Triangle

Easy

119. Pascal's Triangle II

Easy

120. Triangle

Med.

121. Best Time to Buy and Sell Stock

Easy

122. Best Time to Buy and Sell Stock II

Med.

123. Best Time to Buy and Sell Stock III

Hard

124. Binary Tree Maximum Path Sum

Hard

125. Valid Palindrome

Easy

126. Word Ladder II

Hard

127. Word Ladder

Hard

128. Longest Consecutive Sequence

Med.

129. Sum Root to Leaf Numbers

Med.

130. Surrounded Regions

Med.

131. Palindrome Partitioning

Med.

132. Palindrome Partitioning II

Hard

133. Clone Graph

Med.

134. Gas Station

Med.

135. Candy

Hard

136. Single Number

Easy

137. Single Number II

Med.

138. Copy List with Random Pointer

Med.

139. Word Break

Med.

140. Word Break II

Hard

141. Linked List Cycle

Easy

142. Linked List Cycle II

Med.

143. Reorder List

Med.

144. Binary Tree Preorder Traversal

Easy

145. Binary Tree Postorder Traversal

Easy

146. LRU Cache

Med.

147. Insertion Sort List

Med.

148. Sort List

Med.

149. Max Points on a Line

Hard

150. Evaluate Reverse Polish Notation

Med.

Remove distracting text, extract the programming question, provide simple, common, and optimized Java solution for it.