1. 数组（Vector）问题

1. 数组访问越界

• 报错内容：

  =================================================================
  ==42==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000003c0 at pc 0x00000034b87d bp 0x7ffd50c49a80 sp 0x7ffd50c49a78
  READ of size 4 at 0x6020000003c0 thread T0
      #2 0x7f1c8493a0b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
  0x6020000003c0 is located 0 bytes to the right of 16-byte region [0x6020000003b0,0x6020000003c0)
  allocated by thread T0 here:
      #6 0x7f1c8493a0b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
  Shadow bytes around the buggy address:
    0x0c047fff8020: fa fa fd fa fa fa fd fd fa fa fd fa fa fa fd fa
    0x0c047fff8030: fa fa fd fa fa fa fd fa fa fa fd fd fa fa fd fa
    0x0c047fff8040: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fd
    0x0c047fff8050: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
    0x0c047fff8060: fa fa fd fd fa fa fd fa fa fa fd fa fa fa fd fa
  =>0x0c047fff8070: fa fa fd fa fa fa 00 00[fa]fa fa fa fa fa fa fa
    0x0c047fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
    0x0c047fff8090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
    0x0c047fff80a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
    0x0c047fff80b0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
    0x0c047fff80c0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  Shadow byte legend (one shadow byte represents 8 application bytes):
    Addressable:           00
    Partially addressable: 01 02 03 04 05 06 07 
    Heap left redzone:       fa
    Freed heap region:       fd
    Stack left redzone:      f1
    Stack mid redzone:       f2
    Stack right redzone:     f3
    Stack after return:      f5
    Stack use after scope:   f8
    Global redzone:          f9
    Global init order:       f6
    Poisoned by user:        f7
    Container overflow:      fc
    Array cookie:            ac
    Intra object redzone:    bb
    ASan internal:           fe
    Left alloca redzone:     ca
    Right alloca redzone:    cb
    Shadow gap:              cc
  ==42==ABORTING
  

• 原程序

  class Solution {
  public:
      int findBestValue(vector<int>& arr, int target) {
  
  	sort(arr.begin(),arr.end());
      
  	int n = arr.size();
  	int i = 0, sum = 0, sum_tmp = 0, res;
  	while (sum < target) {
  		if (i == 0)
  			sum = n * arr[i];
  		else {
  			sum_tmp += arr[i - 1];
  			sum = sum_tmp + n * arr[i];
  		}
  		i++; n--;
  	}
  	res = ((target - sum_tmp) / (n + 1)) + 1;
  
  	int res_err1,res_err2;
  	res_err1 = abs(target - (sum_tmp + res * (n + 1)));
  	res_err2 = abs(target - (sum_tmp + (res - 1)*(n + 1)));
  	if (res_err1 < res_err2)
  		return res;
  	else
  		return res - 1;
      }
  };
  

• 原因：

  • Leetcode使用了Address Sanitizer检查了是否存在内存非法访问；

  • 在程序中，因为while循环中没有考虑arr数组索引值越界的情况，导致报此错误。

• 修正后程序：

  class Solution {
  public:
      int findBestValue(vector<int>& arr, int target) {
  
  	sort(arr.begin(),arr.end());
      
  	int n = arr.size();
  	int i = 0, sum = 0, sum_tmp = 0, res;
  	while (sum < target) {
  		if (i == 0)
  			sum = n * arr[i];
          else if(n == 0)
              break;
  		else {
  			sum_tmp += arr[i - 1];
  			sum = sum_tmp + n * arr[i];
  		}
  		i++; n--;
  	}
  	res = ((target - sum_tmp) / (n + 1)) + 1;
  
  	int res_err1,res_err2;
  	res_err1 = abs(target - (sum_tmp + res * (n + 1)));
  	res_err2 = abs(target - (sum_tmp + (res - 1)*(n + 1)));
  	if (res_err1 < res_err2)
  		return res;
  	else
  		return res - 1;
      }
  };