两数之和#1（简单）
public int[] twoSum(int[] nums, int target) {//法一:暴力法.时间复杂度O(n^2),空间复杂度O(1)int n = nums.length;for (int i = 0; i < n - 1; ++i) {for (int j = i + 1; j < n; ++j) {if (nums[i] + nums[j] == target) {return new int[]{i, j};}}}return null;}public int[] twoSum(int[] nums, int target) {//法二:哈希表.时间复杂度O(n),空间复杂度O(n)HashMap<Integer, Integer> map = new HashMap<>();int n = nums.length;for (int i = 0; i < n; ++i) {int another = target - nums[i];if (map.containsKey(another)) {return new int[]{i, map.get(another)};}map.put(nums[i], i);}return null;}
func twoSum(nums []int, target int) []int {
// 法一:暴力法.时间复杂度O(n^2),空间复杂度O(1)
n := len(nums)
for i := 0; i < n - 1; i++ {
for j := i + 1; j < n; j++ {
if nums[i] + nums[j] == target {
return []int{i, j}
}
}
}
return nil
}
func twoSum(nums []int, target int) []int {
// 法二:哈希表.时间复杂度O(n),空间复杂度O(n)
tempMap := make(map[int]int)
for i := 0; i < len(nums); i++ {
another := target - nums[i]
if _, ok := tempMap[another]; ok {
return []int{tempMap[another], i}
}
tempMap[nums[i]] = i
}
return nil
}
盛水最多的容器#11（中等）
public int maxArea(int[] height) {
//方法一：暴力解法,双重遍历.时间复杂度O(n^2),空间复杂度O(1)
//超时，所以没有ac。但是思路是对的
int length = height.length;
int maxArea = 0;
for (int i = 0; i < length - 1; ++i) {
for (int j = i + 1; j < length; ++j) {
//最短的边 * 长度就是当前的面积。
int minHeight = Math.min(height[i], height[j]);
maxArea = Math.max(minHeight * (j - i), maxArea);
}
}
return maxArea;
}
public int maxArea(int[] height) {
//方法二：双指针,一遍遍历.时间复杂度O(n),空间复杂度O(1)
//从两边往中间靠近，由于两指针间距在减小
//只能高度增加，面积才可能更大
int left = 0, right = height.length - 1;
int maxArea = 0;
while (left < right) {
//面积同样取决于两板之间最低的那根
int minHeight = height[left] < height[right] ? height[left++] : height[right--];
int area = minHeight * (right - left + 1);
maxArea = Math.max(area, maxArea);
}
return maxArea;
}
func maxArea(height []int) int {
//方法一：暴力解法,双重遍历.时间复杂度O(n^2),空间复杂度O(1)，超时
n := len(height)
maxArea := 0
for i := 0; i < n - 1; i++ {
for j := i + 1; j < n; j++ {
width := minOne(height[i], height[j])
area := (j - i) * width
maxArea = maxOne(area, maxArea)
}
}
return maxArea
}
func maxArea(height []int) int {
//方法二：双指针,一遍遍历.时间复杂度O(n),空间复杂度O(1)
//从两边往中间靠近，由于两指针间距在减小
//只能高度增加，面积才可能更大
n := len(height)
maxArea := 0
left := 0
right := n -1
for left < right {
width := 0
if height[left] < height[right] {
width = height[left]
left++
} else {
width = height[right]
right--
}
maxArea = maxOne(maxArea, width * (right - left + 1))
}
return maxArea
}
func maxOne(a, b int) int {
if a < b {
return b
}
return a
}
func minOne(a, b int) int {
if a < b {
return a
}
return b
}
三数之和#15（中等）
//三重for循环思路肯定是可以的，但是一定会超时，所以要用其他的方法
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
//排序+双指针,时间复杂度O(n2),空间复杂度O(logn)
//先排序，保证不会重复
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
int n = nums.length;
for (int i = 0; i < n; i++) {
//跳过重复的部分
if (i > 0 && nums[i] == nums[i-1]) continue;
int left = i + 1, right = n - 1;
while (left < right) {
if (nums[left] + nums[right] + nums[i] == 0) {
ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
} else if (nums[left] + nums[right] + nums[i] < 0) {
left++;
} else {
right--;
}
}
}
return ans;
}
}
//其实这里直接用hashset去做去重也是可以的，这样就可以不用写continue和内层两个while了。
//但是这个执行时间就肯定比不上上面的方法了。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
//排序+双指针,时间复杂度O(n2),空间复杂度O(logn)
//先排序，保证不会重复
Set<List<Integer>> res = new HashSet<>();
Arrays.sort(nums);
int n = nums.length;
for (int i = 0; i < n; i++) {
int left = i + 1, right = n - 1;
while (left < right) {
if (nums[left] + nums[right] + nums[i] == 0) {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
right--;
} else if (nums[left] + nums[right] + nums[i] < 0) {
left++;
} else {
right--;
}
}
}
List<List<Integer>> ans = new ArrayList<>();
ans.addAll(res);
return ans;
}
}
最接近的三数之和#16（中等）
class Solution {
public int threeSumClosest(int[] nums, int target) {
//和15题类似，排序加双指针,时间复杂度O(n2),空间复杂度O(logn)
int ans = nums[0] + nums[1] + nums[2];
int n = nums.length;
Arrays.sort(nums);
for (int i = 0; i < n; i++) {
int l = i + 1, r = n - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum == target) return sum;
if (Math.abs(sum - target) < Math.abs(ans - target)) ans = sum;
if (sum < target) l++;
else r--;
}
}
return ans;
}
}
四数之和#18（中等）
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
//排序+双指针,时间复杂度O(n3),空间复杂度O(logn)
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
int n = nums.length;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue;
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j-1]) continue;
int twoSum = nums[i] + nums[j];
int l = j + 1, r = n - 1;
while (l < r) {
if (twoSum + nums[l] + nums[r] == target) {
ans.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
while (l < r && nums[l] == nums[l+1]) l++;
while (l < r && nums[r] == nums[r-1]) r--;
l++;
r--;
} else if (twoSum + nums[l] + nums[r] < target) {
l++;
} else {
r--;
}
}
}
}
return ans;
}
}
//这个还可以剪纸，在时间上做优化，比如说如果两/三数之和就大于target了，就直接break掉。
//官方题解中，如果第一个数加上倒数三个最大的数还是小于target，或者第一二个数加倒数两个数还是小于target就直接continue掉。进入下一层i/j的循环。
接雨水#42（困难）
class Solution {
public int trap(int[] height) {
//法一:按行求.求出每一行接水量，然后累加
//时间复杂度O(m*n),m是最大高度,n是数组长度。约等于n^2所以会超时。
//空间复杂度O(1)。
//当出现第一个高度大于等于行数的开始更新，
//之后高度小于行数则接水量+1，直到高度大于等于行数则加入到总量中。
//总共水量sum
int sum = 0;
//先求出最大高度，也即是行数，也就是最外层循环的次数
int maxHeight = 0;
for (int i = 0; i < height.length; i++) {
maxHeight = maxHeight > height[i] ? maxHeight : height[i];
}
//最外层循环，求每一层的积水量
for (int i = 1; i <= maxHeight; ++i) {
//标记是否开始更新temp
boolean isStart = false;
int temp = 0;
for (int j = 0; j < height.length; ++j) {
if (isStart && height[j] < i) {
temp++;
}
if (height[j] >= i) {
sum += temp;
temp = 0;
isStart = true;
}
}
}
return sum;
}
}
//=======================================================================
class Solution {
public int trap(int[] height) {
//法二:按列求。
//时间复杂度O(n^2),空间复杂度O(1)
int sum = 0;
//最两边的列是没有办法接到水的
for (int i = 1; i < height.length - 1; i++) {
//找出左边的最高棒子
int maxLeft = 0;
for (int j = i - 1; j >= 0; --j) {
if (height[j] > maxLeft) {
maxLeft = height[j];
}
}
//找出右边最高的棒子
int maxRight = 0;
for (int j = i + 1; j < height.length; ++j) {
//本来想三目运算符一句话写完。但是每一次三目运算符都有赋值运算。还是觉得这样更好
if (height[j] > maxRight) {
maxRight = height[j];
}
}
//找出两端最小值
int minHeight = Math.min(maxLeft, maxRight);
if (minHeight > height[i]) {
sum = sum + (minHeight - height[i]);
}
}
return sum;
}
}
//==========================================================================
class Solution {
public int trap(int[] height) {
//法三:动态规划。利用两个数组记录当前列的左边最高和右边最高。
//时间复杂度O(n),空间复杂度O(n)
int sum = 0;
int n = height.length;
int[] maxLeftArray = new int[n];
int[] maxRightArray = new int[n];
//求出左边最高列数组
for (int i = 1; i < n; i++) {
maxLeftArray[i] = Math.max(maxLeftArray[i - 1], height[i - 1]);
}
//求出右边最高列的数组
for (int i = n - 2; i > 0; --i) {
maxRightArray[i] = Math.max(maxRightArray[i + 1], height[i + 1]);
}
for (int i = 1; i < n - 1; ++i) {
int minHeight = Math.min(maxLeftArray[i], maxRightArray[i]);
if (minHeight > height[i]) {
sum += minHeight - height[i];
}
}
return sum;
}
}
//=========================================================================
class Solution {
public int trap(int[] height) {
//法四:双指针。时间复杂度O(n),空间复杂度O(1)
int n = height.length;
int sum = 0;
int maxLeft = 0;
int maxRight = 0;
int left = 1;
int right = n - 2;//加右指针进去
for (int i = 1; i < n - 1; i++) {
//对于左边，左边最高是可信的，对于右边，右边最高是可信的
//所以左边最高小于右边最高时就可以确定自己能装多少水了
if (height[left - 1] < height[right + 1]) {
//从左到右更新
maxLeft = Math.max(maxLeft, height[left - 1]);
int min = maxLeft;
if (min > height[left]) {
sum = sum + (min - height[left]);
}
left++;
} else {
//从右到左更新
maxRight = Math.max(maxRight, height[right + 1]);
int min = maxRight;
if (min > height[right]) {
sum = sum + (min - height[right]);
}
right--;
}
}
return sum;
}
}
//=========================================================================
class Solution {
public int trap(int[] height) {
//法五:单调栈。时间复杂度O(n),空间复杂度O(n)
int sum = 0;
Deque<Integer> stack = new LinkedList<>();
int n = height.length;
for (int i = 0; i < n; ++i) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop();
if (stack.isEmpty()) {
break;
}
int left = stack.peek();
int currWidth = i - left - 1;
int currHeight = Math.min(height[left], height[i]) - height[top];
sum += currWidth * currHeight;
}
stack.push(i);
}
return sum;
}
}
若有收获，就点个赞吧
0 人点赞
