Closed congr closed 5 years ago
O(N), very tricky - watch out overflow cases
public class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> res = new ArrayList<>();
long prev = (long)lower - 1; // int -> long !!!
long curr = 0;
for(int i = 0; i <= nums.length; i++) {
curr = i == nums.length ? (long)upper + 1: (long)nums[i]; // int -> long
if(curr - prev == 2) res.add((prev + 1) + "");
else if(curr - prev > 2) res.add((prev + 1) + "->" + (curr - 1));
prev = curr;
}
return res;
}
}
The first accepted code. 0ms
class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> list = new ArrayList();
if (nums.length == 0) {
String t = range((long)upper+1, (long)lower-1);
if (!t.isEmpty()) list.add(t);
return list;
}
String t = range((long)nums[0], (long)lower-1);
if (!t.isEmpty()) list.add(t);
for (int i = 1; i<nums.length; i++) {
t = range((long)nums[i], (long)nums[i-1]); // a, b
if (!t.isEmpty()) list.add(t);
}
t = range((long)upper+1, (long)nums[nums.length-1]);
if (!t.isEmpty()) list.add(t);
return list;
}
// [2147483647] 0 2147483647
String range(long a, long b) { // a>b
if (a - b == 2)
return String.valueOf(b + 1);
else if (a - b > 2)
return String.valueOf((b + 1) + "->" + (a - 1));
else
return "";
}
}
https://leetcode.com/problems/missing-ranges/