526互联

[LeetCode] 1262. Greatest Sum Divisible by Three

发布时间 2023-06-20 04:36:28作者: CNoodle

Given an integer array nums, return the maximum possible sum of elements of the array such that it is divisible by three.

Example 1:

Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2:

Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:

Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

Constraints:

  • 1 <= nums.length <= 4 * 104
  • 1 <= nums[i] <= 104

可被三整除的最大和。

给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。

这道题的最优解是用 DP 做但是我没有很理解，这里我给出一个次优解，思路是贪心。

既然是找最大的和，那么首先我们可以看一下把整个数组都加起来的和 sum 是否能 % 3，如果 sum % 3 == 0，那么就无须减去任何元素。

比较一般的 case 是 sum % 3 != 0，我们可以创建两个数组 a 和 b，一个放 % 3 == 1 的所有元素，另一个放 % 3 == 2 的所有元素。

  • 如果 sum % 3 == 1，需要减去的是数组 a 里面最小的数字（这个数字 % 3 == 1）；或者如果数组 b 里面超过两个元素，我们减去 b 里最小的两个元素（这两个元素的和 % 3 == 1）。这两种情况取较小值
  • 如果 sum % 3 == 2，如果 b 不为空，直接减去 b 中最小数字（这个数字 % 3 == 2）；或者 a 中也有至少两个数字，那么减去 a 里最小的两个元素（这两个元素的和 % 3 == 2）。这两种情况取较小值

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int maxSumDivThree(int[] nums) {
 3         int sum = 0;
 4         for (int num : nums) {
 5             sum += num;
 6         }
 7         // corner case
 8         if (sum % 3 == 0) {
 9             return sum;
10         }
11 
12         // normal case
13         List<Integer> a = new ArrayList<>();
14         List<Integer> b = new ArrayList<>();
15         for (int num : nums) {
16             if (num % 3 == 1) {
17                 a.add(num);
18             } else if (num % 3 == 2) {
19                 b.add(num);
20             }
21         }
22         Collections.sort(a);
23         Collections.sort(b);
24 
25         if (sum % 3 == 2) {
26             List<Integer> temp = a;
27             a = b;
28             b = temp;
29         }
30         int res = a.isEmpty() ? 0 : sum - a.get(0);
31         if (b.size() > 1) {
32             res = Math.max(res, sum - b.get(0) - b.get(1));
33         }
34         return res;
35     }
36 }

 

LeetCode 题目总结